Numeración de permutación

9

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

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
Kyle McCormick
fuente
1
¿Podemos tener más tiempo hasta que se elija un ganador? Tres días es muy poco tiempo.
xnor

Respuestas:

4

GolfScript, 12 (22 caracteres - 10 bonus)

~]0\.,{.,@*\.(@$?@+\}*

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 .

Howard
fuente
Jaja, no era exactamente lo que estaba buscando cuando dije "sin usar factoriales", pero supongo que cuenta. Felicitaciones
Kyle McCormick
4

CJam, 31, con factoriales

q~]{__(f<0+:+\,,(;1+:**\(;}h]:+
jimmy23013
fuente
¿Por qué sigo recibiendo votos? La respuesta de GolfScript se puede reescribir en CJam con solo 23 caracteres.
jimmy23013
66
Porque a la gente le gusta tu respuesta.
seequ
1

Python 2 (77 = 87-10)

p=map(int,raw_input().split())
s=0
while p:s=s*len(p)+sorted(p).index(p.pop(0))
print s

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 para print) porque en Python 3 map(int,...)produce un objeto de mapa, que no admite operaciones de lista,

xnor
fuente
1

Pyth (13 = 23-10)

JVPwdWJ=Z+*ZlJXovNJ;J)Z

Un puerto de mi respuesta Python .

Una traducción de Python (con algunas cosas irrelevantes filtradas):

Z=0
J=rev(split(input()," "))
while J:
 Z=plus(times(Z,len(J)),index(order(lambda N:eval(N),J),J.pop()))
print(Z)

Los números de entrada permanecen cadenas pero se ordenan como ints usando eval como la clave. La lista se invierte de modo que poptoma el frente en lugar del reverso.

xnor
fuente
1

Cobra - 202

Obviamente Cobra no está realmente compitiendo en este.

class P
    var n=0
    var t=CobraCore.commandLineArgs[1:]
    def main
        .f(.t[0:0])
    def f(l as List<of String>)
        if.t.count==l.count,print if(.t<>l,'',.n+=1)
        else,for i in.t.sorted,if i not in l,.f(l+[i])
Οurous
fuente
0

J, 5 bytes (15-10)

#\.#.+/@(<{.)\.

Esto se ejecuta en tiempo O ( n 2 ) y es capaz de manejar n = 100 fácilmente.

Uso

   f =: #\.#.+/@(<{.)\.
   f 0 1 2
0
   f 0 2 1
1
   f 1 0 2
2
   f 1 2 0
3
   f 2 0 1
4
   f 2 1 0
5
   f 0 1 2 3 4 5 6 7
0
   f 0 1 2 3 4 5 7 6
1
   f 0 1 2 3 4 6 5 7
2
   f 1 3 5 17
0
   f 781 780 779 13
23
   f 81 62 19 12 11 8 2 0
40319
   f 195 124 719 1 51 6 3
4181
   NB. A. is the builtin for permutation indexing
   timex 'r =: f 927 A. i. 100'
0.000161
   r
927

Explicación

#\.#.+/@(<{.)\.  Input: array P
             \.  For each suffix of P
          {.       Take the head
         <         Test if it is greater than each of that suffix
     +/@           Sum, count the number of times it is greater
#\.              Get the length of each suffix of P
   #.            Convert to decimal using a mixed radix
millas
fuente