Introducción

Supongamos que se le entrega una permutación aleatoria de nobjetos. La permutación está sellada en una caja, por lo que no tienes idea de cuál es la n!posible. Si logró aplicar la permutación a nobjetos distintos, podría deducir inmediatamente su identidad. Sin embargo, solo se le permite aplicar la permutación a nvectores binarios de longitud , lo que significa que tendrá que aplicarla varias veces para reconocerla. Claramente, aplicarlo a los nvectores con solo uno 1hace el trabajo, pero si eres inteligente, puedes hacerlo con log(n)aplicaciones. Sin embargo, el código para ese método será más largo ...

Este es un desafío experimental en el que su puntaje es una combinación de longitud de código y complejidad de consulta , lo que significa la cantidad de llamadas a un procedimiento auxiliar. La especificación es un poco larga, así que tengan paciencia conmigo.

La tarea

Su tarea es escribir una función con nombre (o el equivalente más cercano) f que tome como entradas un número entero positivo ny una permutación pde los primeros nnúmeros enteros, usando indexación basada en 0 o en 1. Su salida es la permutación p. Sin embargo, no puede acceder a la permutación pdirectamente . Lo único que puede hacer con él es aplicarlo a cualquier vector de nbits. Para este propósito, utilizará una función auxiliar Pque toma una permutación py un vector de bits v, y devuelve el vector permutado cuya p[i]coordenada th contiene el bit v[i]. Por ejemplo:

P([1,2,3,4,0], [1,1,0,0,0]) == [0,1,1,0,0]

Puede reemplazar "bits" con dos valores distintos, como 3and -4, or 'a'y 'b', y no necesitan ser reparados, por lo que puede llamar Pcon ambos [-4,3,3,-4]y [2,2,2,1]en la misma llamada a f. La definición de Pno se cuenta para su puntaje.

Puntuación

La complejidad de la consulta de su solución en una entrada dada es la cantidad de llamadas que realiza a la función auxiliar P. Para que esta medida no sea ambigua, su solución debe ser determinista. Puede usar números generados de forma seudoaleatoria, pero también debe arreglar una semilla inicial para el generador.

En este repositorio encontrará un archivo llamado permutations.txtque contiene 505 permutaciones, 5 de cada longitud entre 50 y 150 inclusive, usando indexación basada en 0 (incremente cada número en el caso basado en 1). Cada permutación está en su propia línea, y sus números están separados por espacios. Su puntaje es el recuento de bytes de f+ complejidad de consulta promedio en estas entradas . La puntuación más baja gana.

Reglas extra

Se prefiere el código con explicaciones, y las lagunas estándar no están permitidas. En particular, los bits individuales son indistinguibles (por lo que no puede dar un vector de Integerobjetos Py comparar sus identidades), y la función Psiempre devuelve un nuevo vector en lugar de reorganizar su entrada. Puede cambiar libremente los nombres de fy P, y el orden en que toman sus argumentos.

Si es la primera persona en responder en su lenguaje de programación, le recomendamos encarecidamente que incluya un arnés de prueba, incluida una implementación de la función Pque también cuente la cantidad de veces que se llamó. Como ejemplo, aquí está el arnés para Python 3.

def f(n,p):
    pass # Your submission goes here

num_calls = 0

def P(permutation, bit_vector):
    global num_calls
    num_calls += 1
    permuted_vector = [0]*len(bit_vector)
    for i in range(len(bit_vector)):
        permuted_vector[permutation[i]] = bit_vector[i]
    return permuted_vector

num_lines = 0
file_stream = open("permutations.txt")
for line in file_stream:
    num_lines += 1
    perm = [int(n) for n in line.split()]
    guess = f(len(perm), perm)
    if guess != perm:
        print("Wrong output\n %s\n given for input\n %s"%(str(guess), str(perm)))
        break
else:
    print("Done. Average query complexity: %g"%(num_calls/num_lines,))
file_stream.close()

En algunos idiomas, es imposible escribir tal arnés. En particular, Haskell no permite que la función pura Pregistre la cantidad de veces que se llama. Por este motivo, puede volver a implementar su solución de tal manera que también calcule su complejidad de consulta y la use en el arnés.

J, 44.0693 22.0693 = 37 15 + 7.06931

Si no podemos llamar Pen i. n, al menos podemos llamada Pen cada bit de i. nforma separada. El número de invocaciones de Pes >. 2 ^. n(⌈log ₂  n ⌉). Creo que esto es óptimo.

f=:P&.|:&.#:@i.

Aquí hay una implementación de la función Pque usa el vector de permutación py guarda el número de invocaciones Pinv.

P =: 3 : 0"1
 Pinv =: Pinv + 1
 assert 3 > # ~. y    NB. make sure y is binary
 p { y
)

Aquí hay un arnés de prueba que recibe una permutación y devuelve el número de invocaciones de p:

harness =: 3 : 0
 Pinv =: 0
 p =: y
 assert y = f # y     NB. make sure f computed the right permutation
 Pinv
)

Y así es como puede usarlo en el archivo permutations.txt:

NB. average P invocation count
(+/ % #) harness@".;._2 fread 'permutations.txt'

Explicación

La breve explicación ya se proporcionó anteriormente, pero aquí hay una más detallada. Primero, fcon espacios insertados y como una función explícita:

f =: P&.|:&.#:@i.
f =: 3 : 'P&.|:&.#: i. y'

Leer:

Deje f ser P bajo transposición bajo representación de base 2 de los primeros enteros y .

donde y es el parámetro formal de f. en J, los parámetros de a (función) se denominan x e y si el verbo es diádico (tiene dos parámetros) e y si es monádico (tiene un parámetro).

En lugar de invocar Pen i. n(es decir 0 1 2 ... (n - 1)), invocamos Pen cada posición de bit de los números en i. n. Como todas las permutaciones permutan de la misma manera, podemos volver a ensamblar los bits permutados en números para obtener un vector de permutación:

• i. y- enteros de 0a y - 1.

• #: y- yrepresentado en la base 2. Esto se extiende a los vectores de números de forma natural. Por ejemplo, #: i. 16produce:

  0 0 0 0
  0 0 0 1
  0 0 1 0
  0 0 1 1
  0 1 0 0
  0 1 0 1
  0 1 1 0
  0 1 1 1
  1 0 0 0
  1 0 0 1
  1 0 1 0
  1 0 1 1
  1 1 0 0
  1 1 0 1
  1 1 1 0
  1 1 1 1
  

• #. y- yInterpretado como un número base 2. Notablemente, esto es lo contrario a #:; y ~: #. #:siempre tiene.

• |: y- ytranspuesto.

• u&.v y- udebajo v, ahí es vinv u v ydonde vinvestá el inverso a v. Tenga en cuenta que |:es su propio inverso.

• P y- la función Paplicada a cada vector ypor definición.

Pyth 32 + 7.06931 = 37.06931

Encontré el siguiente algoritmo completamente independiente. Pero es más o menos lo mismo que la solución J muy corta de FUZxxl (por lo que yo entiendo).

Primero, la definición de la función P, que permuta una matriz de bits de acuerdo con una permutación desconocida.

D%GHJHVJ XJ@HN@GN)RJ

Y luego el código, que determina la permutación.

Mmxmi_mbk2Cm%dHCm+_jk2*sltG]0GdG

Esto define una función g, que toma dos argumentos. Puedes llamarlo por g5[4 2 1 3 0. Aquí hay una demostración en línea . Nunca usé tantos (5) mapas anidados.

Por cierto, no he hecho un arnés de prueba. La función tampoco Pcuenta cuántas veces la llamo. Ya pasé mucho tiempo descubriendo el algoritmo. Pero si lees mi explicación, es bastante obvio que usa int(log2(n-1)) + 1llamadas ( = ceil(log2(n))). Y sum(int(log2(n-1)) + 1 for n in range(50, 151)) / 101.0 = 7.069306930693069.

Explicación:

En realidad, me costó bastante encontrar este algoritmo. No me quedó claro en absoluto cómo lograrlo log(n). Entonces comencé a hacer algunos experimentos con pequeños n.

Primera nota: una matriz de bits recopila la misma información que la matriz de bits complementaria. Por lo tanto, todas las matrices de bits en mi solución tienen como máximo n/2bit activo.

n = 3:

Como solo podemos usar una matriz de bits con 1 bit activo, la solución óptima depende de dos llamadas. Por ejemplo P([1, 0, 0])y P([0, 1, 0]). Los resultados nos dicen el primer y segundo número de la permutación, indirectamente obtenemos el tercero.

n = 4:

Aquí se pone un poco interesante. Ahora podemos usar dos tipos de matriz de bits. Aquellos con 1 bit activo y aquellos con 2 bits activos. Si usamos una matriz de bits con un bit activo, solo recopilamos información sobre un número de la permutación y volvemos a n = 3, lo que resulta en 1 + 2 = 3llamadas de P. La parte interesante es que podemos hacer lo mismo con solo 2 llamadas, si utilizamos matrices de bits con 2 bits activos. Por ejemplo P([1, 1, 0, 0])y P([1, 0, 1, 0]).

Digamos que obtenemos los resultados [1, 0, 0, 1]y [0, 0, 1, 1]. Vemos que el bit número 4 está activo en ambas matrices de salida. El único bit que estaba activo en ambas matrices de entrada era el bit número 1, por lo que claramente comienza la permutación 4. Ahora es fácil ver que el bit 2 se movió al bit 1 (primera salida) y el bit 3 se movió al bit 3 (segunda salida). Por lo tanto, la permutación debe ser [4, 1, 3, 2].

n = 7:

Ahora algo más grande. Mostraré las llamadas de Pinmediato. Son la única vez que se me ocurrió después de pensar un poco y experimentar. (Tenga en cuenta que estos no son los que uso en mi código).

P([1, 1, 1, 0, 0, 0, 0])
P([1, 0, 0, 1, 1, 0, 0])
P([0, 0, 1, 1, 0, 1, 0])

Si en las primeras dos matrices de salida (y no en la tercera) el bit 2 está activo, sabemos que la permutación mueve el bit 1 al bit 2, ya que el bit uno es el único bit que está activo en las dos primeras matrices de entrada.

Lo importante es que (interpretando las entradas como matriz) cada una de las columnas es única. Esto me recordó en los códigos de Hamming , donde se logra lo mismo. Simplemente toman los números del 1 al 7 y usan su representación de bits como columnas. Usaré los números del 0 al 6. Ahora, lo bueno es que podemos interpretar las salidas (nuevamente las columnas) como números nuevamente. Estos nos dicen el resultado de la permutación aplicada [0, 1, 2, 3, 4, 5, 6].

   0  1  2  3  4  5  6      1  3  6  4  5  0  2
P([0, 1, 0, 1, 0, 1, 0]) = [1, 1, 0, 0, 1, 0, 0]
P([0, 0, 1, 1, 0, 0, 1]) = [0, 1, 1, 0, 0, 0, 1]
P([0, 0, 0, 0, 1, 1, 1]) = [0, 0, 1, 1, 1, 0, 0]

Entonces solo tenemos que rastrear los números. El bit 0 terminó en el bit 5, el bit 1 terminó en el bit 0, el bit 2 terminó en el bit 6, ... Así que la permutación fue [5, 0, 6, 1, 3, 4, 2].

Mmxmi_mbk2Cm%dHCm+_jk2*sltG]0GdG
M                                 define a function g(G, H), that will return
                                  the result of the following computation:
                                  G is n, and H is the permutation. 
                m            G     map each k in [0, 1, ..., Q-1] to:
                  _                   their inverse
                   jk2                binary representation (list of 1s and 0s)
                 +                    extended with 
                      *sltG]0         int(log2(Q - 1)) zeros
               C                   transpose matrix # rows that are longer 
                                                   # than others are shortened
           m%dH                    map each row (former column) d of 
                                   the matrix to the function P (here %)
          C                        transpose back
   m                              map each row k to:                         
    i    2                           the decimal number of the 
     _mbk                            inverse list(k) # C returns tuple :-(
Let's call the result X.  
 m                             G   map each d in [0, 1, ..., Q - 1] to:
  x         X                 d       the index of d in X

Y el código para la función de permutación:

D%GHJHVJ XJ@HN@GN)RJ
D%GH                     def %(G, H):  # the function is called %
    JH                     J = copy(H)
      VJ         )        for N in [0, 1, ..., len(J) - 1]: 
         XJ@HN@GN            J[H[N]] = G[N]           
                  RJ      return J

Mathematica, 63 + 100 = 163

Estoy usando permutaciones basadas en uno, ya que así es como funciona la indexación en Mathematica.

Primero, el arnés de prueba. Esta es la función de consulta p(los nombres definidos por el usuario no deben estar en mayúsculas en Mathematica):

p[perm_, vec_] := (
   i += 1;
   vec[[Ordering@perm]]
   );

Y preparación de entrada junto con el bucle de prueba:

permutations = 
  ToExpression@StringSplit@# + 1 & /@ 
   StringSplit[Import[
     "https://raw.githubusercontent.com/iatorm/permutations/master/permutations.txt"
   ], "\n"];
total = 0;
(
    i = 0;
    result = f@#;
    If[# != result, 
      Print["Wrong result for ", #, ". Returned ," result ", instead."]
    ];
    total += i;
    ) & /@ permutations;
N[total/Length@permutations]

Y finalmente, mi presentación real que usa el algoritmo ingenuo por ahora:

f=(v=0q;v[[#]]=1;Position[q~p~v,1][[1,1]])&/@Range@Length[q=#]&

O con sangría:

f = (
     v = 0 q;
     v[[#]] = 1;
     Position[q~p~v, 1][[1, 1]]
) & /@ Range@Length[q = #] &