El reto
Para un conjunto dado de n enteros, escriba un programa que genere su índice lexicográfico.
Las normas
- La entrada solo debe ser un conjunto de enteros no negativos únicos separados por espacios.
- Debe generar el índice lexicográfico (rango 0 a n! -1 inclusive) de la permutación.
- No se pueden usar bibliotecas de permutación ni elementos integrados de permutación.
- No puede generar el conjunto de permutaciones o cualquier subconjunto de permutaciones de la entrada para ayudarlo a encontrar el índice.
- Tampoco puede aumentar o disminuir la permutación dada a la permutación siguiente / anterior (lexicográficamente).
- Puntos de bonificación (-10 bytes) si encuentra alguna forma de completar esto sin usar factoriales.
- El tiempo de ejecución debe ser inferior a 1 minuto para n = 100
- El código más corto por conteo de bytes gana
- Ganador elegido el martes (22 de julio de 2014)
Más acerca de las permutaciones
- http://www.monkeyphysics.com/articles/read/26/numbering_permutations.html
- Operación de grupo de permutación
- http://lin-ear-th-inking.blogspot.com/2012/11/enumerating-permutations-using.html
Ejemplos
0 1 2 --> 0
0 2 1 --> 1
1 0 2 --> 2
1 2 0 --> 3
2 0 1 --> 4
2 1 0 --> 5
0 1 2 3 4 5 6 7 --> 0
0 1 2 3 4 5 7 6 --> 1
0 1 2 3 4 6 5 7 --> 2
1 3 5 17 --> 0
781 780 779 13 --> 23
81 62 19 12 11 8 2 0 --> 40319
195 124 719 1 51 6 3 --> 4181
code-golf
math
combinatorics
set-theory
permutations
Kyle McCormick
fuente
fuente
Respuestas:
GolfScript, 12 (22 caracteres - 10 bonus)
Puntos de bonificación por no usar factoriales. La entrada debe darse en STDIN en el formato descrito en la pregunta. Puedes probar el código en línea .
fuente
CJam, 31, con factoriales
fuente
Python 2 (77 = 87-10)
Tan legible. Mucho incorporado. Guau.
Utilizamos el hecho de que el índice lexicográfico de una permutación es la suma sobre los elementos de las permutaciones del número de inversiones por encima de ese elemento (valores después de él pero debajo de él) multiplicado por el factorial del número de elementos después de él. En lugar de evaluar esta expresión de tipo polinomial término por término, usamos algo similar al método de Horner .
En lugar de recorrer los índices de la matriz, eliminamos repetidamente el primer elemento de la lista y procesamos los elementos restantes. La expresión
sorted(p).index(p.pop(0))
cuenta el número de inversiones más allá del primer índice tomando su posición en la lista ordenada, mientras que al mismo tiempo realiza la eliminación.Lamentablemente, tuve que usar Python 2 y tomar 4 caracteres más para
raw_input
(aunque -1 paraprint
) porque en Python 3map(int,...)
produce un objeto de mapa, que no admite operaciones de lista,fuente
Pyth (13 = 23-10)
Un puerto de mi respuesta Python .
Una traducción de Python (con algunas cosas irrelevantes filtradas):
Los números de entrada permanecen cadenas pero se ordenan como ints usando eval como la clave. La lista se invierte de modo que
pop
toma el frente en lugar del reverso.fuente
Cobra - 202
Obviamente Cobra no está realmente compitiendo en este.
fuente
J, 5 bytes (15-10)
Esto se ejecuta en tiempo O ( n 2 ) y es capaz de manejar n = 100 fácilmente.
Uso
Explicación
fuente