Encontrar la n-ésima permutación lexicográfica de una cadena

Question

Tengo un conjunto ordenado de símbolos S = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }. Quiero encontrar la permutación 1.000.000-ésima en orden lexicográfico de S. Es un rompecabezas de programación, pero quería encontrar una manera sin forzar la tarea.

Así que mi pensamiento era el siguiente:

Para 10 posiciones de símbolos variables, tenemos 10! permutaciones, obviamente. Ahora queremos encontrar el primer símbolo.

Si fijamos el primer símbolo, los 9 símbolos restantes pueden tener 9 combinaciones.

Esto significa que el 0 o el 1 no pueden ser el primer símbolo, porque la posición más alta posible es 2*9! = 725.760, que es inferior a 1.000.000.

¡La posición más baja para un 3 inicial es 3*9! + 1 = 1.088.641, por lo que tampoco puede ser 3 ni superior.

Por lo tanto, el primer número debe ser 2. ¡2*9! es el mayor múltiplo de 9! no mayor que 1.000.000, así que necesito el segundo símbolo (basado en el cero) del conjunto actual.

Así que ahora la pregunta es, de los restantes S := S \{2}, ¿qué permutación de estos símbolos está en la posición lexicográfica (¡1.000.000 - 2*9!) = 274.240?

6*8! = 241.920 es el mayor múltiplo de 8! que es menor que 274.240, por lo que necesito el 6º símbolo más pequeño del conjunto restante, que es 7. Así que el prefijo debería ser 27 por ahora.

De esta manera, sigo adelante y finalmente llego a: ¡1,000,000 = 2*9! ¡+ 6*8! ¡+ 6*7! ¡+ 2*6! ¡+ 5*5! ¡+ 1*4! ¡+ 2*3! ¡+ 2*2! ¡+ 0*1! ¡+ 0*0!

que resulta en "2783905614" como mi solución.

Sin embargo, según el probador de soluciones (req. registro gratuito) que es incorrecto.

¿En qué me equivoqué al pensar o aplicar?

Answer 1

Para formalizar, si $a_0 < ... < a_n$ , entonces en el $k$ -ésima permutación de $\{a_0, ..., a_n\}$ en orden lexográfico, la entrada principal es $a_q$ si $k = q(n!) + r$ para algunos $q\ge0$ y $0<r\le n!$ . (Nótese que la definición de $r$ aquí es un poco diferente del resto habitual, para el que $0\le r< n!$ . También, $a_q$ es el $(q+1)$ -ésima entrada pero no la $q$ -ésima entrada de la secuencia, ya que el índice comienza en 0).

    [0 1 2 3 4 5 6 7 8 9]
1000000 = 2(9!) + 274240
    2 [0 1 3 4 5 6 7 8 9]
274240 = 6(8!) + 32320
    2 7 [0 1 3 4 5 6 8 9]
32320 = 6*(7!) + 2080
    2 7 8 [0 1 3 4 5 6 9]
2080 = 2*(6!) + 640
    2 7 8 3 [0 1 4 5 6 9]
640 = 5(5!) + 40
    2 7 8 3 9 [0 1 4 5 6]
40 = 1(4!) + 16
    2 7 8 3 9 1 [0 4 5 6]
16 = 2(3!) + 4
    2 7 8 3 9 1 5 [0 4 6]
4 = 1(2!) + 2 <-- we don't write 4 = 2(2!) + 0 here; we need 0<r<=2!
    2 7 8 3 9 1 5 4 [0 6]
2 = 1(1!) + 1
    2 7 8 3 9 1 5 4 6 [0]

Answer 2

Sí, lo he descubierto. Mi planteamiento era correcto, pero me equivoqué de número en 1*4!. Error tonto.

Answer 3

Creo que las soluciones anteriores están ligeramente desviadas. El $k$ -ésima permutación $P_k$ de una cadena $S$ puede calcularse de la siguiente manera (suponiendo un índice de base cero):

• $P_k := \epsilon$
• mientras que $S \neq \epsilon$ :
  • $ f := (|S|-1)!$
  • $i := \lfloor k/f\rfloor$
  • $x := S_i$
  • $k := k \bmod f$
  • adjuntar $x$ a $P_k$
  • eliminar $x$ de $S$
• devolver $P_k$

Esencialmente, esto encuentra el primer elemento de la k-ésima permutación de S, y luego recurre a la cadena restante para encontrar su primer elemento.

Dependiendo de si se empieza a contar las permutaciones desde 0 o desde 1, las respuestas son $(2, 7, 8, 3, 9, 1, 5, 6, 0, 4)$ o $(2, 7, 8, 3, 9, 1, 5, 6, 4, 0)$ .

Aquí hay un poco de código Python, implementando el algoritmo anterior así como su versión recursiva, y luego comprobando la corrección de $\vert S\vert=10$ (puede tardar un poco en ejecutarse):

from math import factorial, floor

# compute the k-th permutation of S (all indices are zero-based)
# all elements in S must be unique

def kthperm(S, k):  #  nonrecursive version
    P = []
    while S != []:
        f = factorial(len(S)-1)
        i = int(floor(k/f))
        x = S[i]
        k = k%f
        P.append(x)
        S = S[:i] + S[i+1:]
    return P

def kthpermrec(S, k):   # recursive version
    P = []
    if S == []:
        return []
    else:
        f = factorial(len(S)-1)
        i = int(floor(k/f))
        return [S[i]] + kthpermrec(S[:i] + S[i+1:], k%f)

if __name__ == "__main__":
    # This creates the k-th permutations for k=0..len(S)!, and then checks that the result is indeed in lexicographic order.

    nrElements = 10
    printout = True
    result = [] # the list of permutations
    for k in xrange(factorial(nrElements)): # loop over all k=0..len(S)!
        S = range(nrElements)    # [0, 1, 2, 3, ... , nrElements-1] 
        p1 = kthperm(S, k)    # compute k-th permutation iteratively
        p2 = kthpermrec(S, k)    # compute k-th permutation recursively
        assert p1==p2       # make sure the recursive and non-recursive function yield the same permutation
        if printout:
            print p1
        result.append(p1)    # add to list of permutations

    for i in xrange(len(result)-1):    # check that permutations are in lexicographic order.
        assert result[i] < result[i+1], "Permutations are not sorted, the code is incorrect."
        assert len(set(result[i])) == len(result[i]), "Permutation contains multiple copies of an element, the code is incorrect."
    assert len(set(result[-1])) == len(result[-1]), "Permutation contains multiple copies of an element, the code is incorrect."    # check on last element
    print "The code is correct for |S| = %d." % nrElements    # This line is only reached if no assertion failed, i.e. all permutations are in lexicographic order.

    print kthperm(range(10), 1000000)
    print kthperm(range(10), 1000001)

Answer 4

Si necesita un programa probador que calcule la permutación a partir del índice o viceversa, puede ver aquí . Puede ser útil y es fácil de usar. Se basa en factoradic.

Como ejemplo: permite calcular el índice correcto correspondiente a la solución "2783905614" mencionada anteriormente O obtener la 2.000.000ª permutación de S = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9 } )

Funciona hasta 17 elementos (índice máximo = 355.687.428.096.000)