Algoritmo para encontrar la permutación numérica dado el índice lexicográfico

Question

Estoy buscando un algoritmo que, dado un conjunto de números (por ejemplo 1 2 3) y un índice (por ejemplo 2), obtenga la segunda permutación de esos números de acuerdo con un orden lexicográfico. Por ejemplo, en este caso, el algoritmo devolverá 1 3 2.

Answer 1

Aquí es una solución simple:

from math import factorial # python math library 

i = 5    # i is the lexicographic index (counting starts from 0) 
n = 3    # n is the length of the permutation 
p = range(1, n + 1) # p is a list from 1 to n 

for k in range(1, n + 1): # k goes from 1 to n 
    f = factorial(n - k) # compute factorial once per iteration 
    d = i // f   # use integer division (like division + floor) 
    print(p[d]),   # print permuted number with trailing space 
    p.remove(p[d])  # delete p[d] from p 
    i = i % f    # reduce i to its remainder 

de salida:

3 2 1 

La complejidad de tiempo es O (n^2) si p es una lista, y O (n) amortizado si p es una tabla hash y factorial está precalculada.

Answer 2

Como no especificó en qué idioma lo quiere, here's an implementation in python.

Solo tiene que obtener el n-ésimo elemento de la secuencia.

Una idea del algoritmo podría ser generar una secuencia que represente un producto cartesiano de la secuencia de entrada e iterarla, omitiendo elementos que tienen elementos repetitivos.

Tenga en cuenta que esta puede no ser la forma más rápida de hacerlo, pero definitivamente es una tarea fácil. Para uno rápido, vea la respuesta de cyborg.

Answer 3

Aquí es una solución de la muestra en la Scala, que voy a explicar en detalle:

/** 
    example: index:=15, list:=(1, 2, 3, 4) 
*/ 
def permutationIndex (index: Int, list: List [Int]) : List [Int] = 
    if (list.isEmpty) list else { 
    val len = list.size  // len = 4 
    val max = fac (len)  // max = 24 
    val divisor = max/len // divisor = 6 
    val i = index/divisor // i = 2 
    val el = list (i) 
    el :: permutationIndex (index - divisor * i, list.filter (_ != el)) } 

Desde Scala no se conoce muy bien, creo que tengo que explicar la última línea del algoritmo, que es , aparte de eso, bastante explicativo.

el :: elist 

construye una nueva lista de un elemento el y una lista elist. Elist es una llamada recursiva.

list.filter (_ != el) 

es solo la lista sin el elemento el.

prueba de manera exhaustiva con una pequeña lista:

(0 to fac (4) - 1).map (permutationIndex (_, List (1, 2, 3, 4))).mkString ("\n") 

Prueba de la velocidad de una lista más grande con 2 ejemplos:

scala> permutationIndex (123456789, (1 to 12).toList) 
res45: List[Int] = List(4, 2, 1, 5, 12, 7, 10, 8, 11, 6, 9, 3) 

scala> permutationIndex (123456790, (1 to 12).toList) 
res46: List[Int] = List(4, 2, 1, 5, 12, 7, 10, 8, 11, 9, 3, 6) 

El resultado aparece inmediatamente en un ordenador portátil 5 años de edad. Hay 479 001 600 permutaciones para una lista de 12 elementos, pero con 100 o 1000 elementos, esta solución aún debería funcionar rápido, solo necesitaría usar BigInt como índice.

¿Cómo funciona? Hice un gráfico, para visualizar el ejemplo, una lista de (1, 2, 3, 4) y un índice de 15:

una lista de 4 elementos produce 4! permutaciones (= 24). Elegimos un índice arbitrario de 0 a 4! -1, digamos 15.

Podemos visualizar todas las permutaciones en un árbol, con el primer nodo desde 1..4. ¡Dividimos 4!por 4 y ver, que cada primer nodo conduce a 6 subárboles. Si dividimos nuestro índice 15 entre 6, el resultado es 2, y el valor en nuestra Lista basada en cero con índice 2 es 3. Entonces, el primer Nodo es 3, y el resto de nuestra Lista es (1, 2, 4) . Aquí hay una tabla que muestra cómo 15 conduce al elemento con el índice 2 en la matriz/Lista/lo que sea:

0 1 2 3 4 5 | 6 ... 11 | 12 13 14 15 16 17 | 18 ... 23 
    0  |  1 |   2   |  3 
      |   | 0 1 2 3 4 5 | 

Ahora restamos 12, el primer elemento de la célula (12 ... 17) para el los últimos 3 elementos, que tienen 6 permutaciones posibles, y vea cómo 15 asigna a 3. El número 3 conduce al índice de matriz 1 ahora, que era el elemento 2, por lo que el resultado hasta ahora es Lista (3, 2, ...) .

     | 0 1 | 2 3 | 4 5 | 
         | 0 | 1 | 3 | 
           | 0 1 | 

Una vez más, restamos 2, y terminan en 2 elementos restantes con 2 permutaciones, y el índice (0, 3), el mapeo de los valores (1, 4). Vemos, que el segundo elemento, que pertenece a la 15 de la parte superior, se asigna a valorar 3, y el elemento restante para el último paso es el otro:

       | 0 | 1 | 
          | 0 | 3 | 
          | 3 | 0 | 

Nuestro resultado es la lista (3, 2, 4 , 1) o los índices (2, 1, 3, 0). Probar todos los índices en orden muestra que ceden todas las permutaciones en orden.

Answer 4

Enlace al artículo menciona:   http://penguin.ewu.edu/~trolfe/#Shuffle

/* Converting permutation index into a permutation 
* From code accompanying "Algorithm Alley: Randomized Shuffling", 
* Dr. Dobb’s Journal, Vol. 25, No. 1 (January 2000) 
* http://penguin.ewu.edu/~trolfe/#Shuffle 
* 
* Author: Tim Rolfe 
*   RolfeT@earthlink.net 
*   http://penguin.ewu.edu/~trolfe/ 
*/ 
#include <stdio.h> 
#include <stdlib.h> 

// http://stackoverflow.com/questions/8940470/algorithm-for-finding-numerical-permutation-given-lexicographic-index 

// Invert the permutation index --- generate what would be 
// the subscripts in the N-dimensional array with dimensions 
// [N][N-1][N-2]...[2][1] 
void IndexInvert(int J[], int N, int Idx) 
{ int M, K; 

    for (M=1, K=N-1; K > 1; K--) // Generate (N-1)! 
     M *= K; 
    for (K = 0; M > 1; K++) 
    { J[K] = Idx/M; // Offset in dimension K 
     Idx = Idx % M; // Remove K contribution 
     M /= --N;   // next lower factorial 
    } 
    J[K] = Idx;   // Right-most index 
} 

// Generate a permutation based on its index/subscript set. 
// To generate the lexicographic order, this involves _shifting_ 
// characters around rather than swapping. Right-hand side must 
// remain in lexicographic order 
void Permute (char Line[], char first, int N, int Jdx[]) 
{ int Limit; 

    Line[0] = first; 
    for (Limit = 1; Limit < N; Limit++) 
     Line[Limit] = (char)(1+Line[Limit-1]); 

    for (Limit = 0; Limit < N; Limit++) 
    { char Hold; 
     int Idx = Limit + Jdx[Limit]; 
     Hold = Line[Idx]; 
     while (Idx > Limit) 
     { Line[Idx] = Line[Idx-1]; 
     Idx--; 
     } 
     Line[Idx] = Hold; 
    } 
} 

// Note: hard-coded to generate permutation in the set [abc... 
int main(int argc, char** argv) 
{ int N = argc > 1 ? atoi(argv[1]) : 4; 
    char *Perm = (char*) calloc(N+1, sizeof *Perm); 
    int *Jdx = (int*) calloc(N, sizeof *Jdx); 
    int Index = argc > 2 ? atoi(argv[2]) : 23; 
    int K, Validate; 

    for (K = Validate = 1; K <= N; K++) 
     Validate *= K; 
    if (Index < 0 || Index >= Validate) 
    { printf("Invalid index %d: %d! is %d\n", Index, N, Validate); 
     return -1; // Error return 
    } 
    IndexInvert(Jdx, N, Index); 
    Permute (Perm, 'a', N, Jdx); 
    printf("For N = %d, permutation %d in [0..%d] is %s\n", 
      N, Index, Validate-1, Perm); 
    return 0;  // Success return 
}