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.Algoritmo para encontrar la permutación numérica dado el índice lexicográfico
Respuesta
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.
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.
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.
+1, por todo el trabajo que le dedicas. –
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
* [email protected]
* 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
}
- 1. Encontrar el número de inversiones de permutación
- 2. Algoritmo para encontrar la siguiente mayor permutación de una cadena dada
- 3. Algoritmo para calcular el horario dado restricciones
- 4. Algoritmo para encontrar el tiempo de inactividad total dado el conjunto de horas de inicio/finalización
- 5. Algoritmo para encontrar rectángulos
- 6. ¿Modificar un número dado para encontrar la suma requerida?
- 7. orden lexicográfico en Java
- 8. Algoritmo para encontrar puntos cercanos?
- 9. algoritmo para encontrar la mejor combinación
- 10. Algoritmo para encontrar grupos óptimos
- 11. Algoritmo para encontrar subconjuntos comunes
- 12. Algoritmo óptimo necesario para encontrar pares divisibles por un número entero dado k
- 13. Delphi - encuentra el personaje en una posición/índice dado
- 14. La conversión de tipo inmediato numérica para numérica tipo genérico
- 15. permutación del conjunto
- 16. Permutación rápida -> número -> algoritmos de asignación de permutación
- 17. ¿Calcular el paso de permutación enésimo?
- 18. Encontrar la fecha para un número de semana dado
- 19. Encontrar un algoritmo para equilibrar este juego
- 20. Objeto de modelo dado, ¿cómo encontrar la ruta de índice en NSTreeController?
- 21. ¿Algún algoritmo eficiente para encontrar las ventanas pangramáticas más pequeñas?
- 22. Necesita ayuda con el algoritmo para resolver el índice a través de la matriz dentada
- 23. algoritmo para números de índice de matriz triangular coeficientes
- 24. ¿Eliminar elementos secundarios dado un índice?
- 25. Algoritmo Bron-Kerbosch para clique encontrar
- 26. Algoritmo para encontrar simetrías de un árbol
- 27. Algoritmo para encontrar píxeles muertos en Javascript
- 28. Algoritmo para encontrar jugadores buenos y confiables
- 29. Algoritmo para encontrar intersecciones entre polilíneas
- 30. Algoritmo rápido para encontrar números primos?
¿Qué has intentado hasta ahora? Un enfoque ingenuo sería generar todas las permutaciones, ordenarlas lexicográficamente y luego elegir la n-ésima. – Gumbo
Sugerencia: Primero encuentre un algoritmo para determinar el primer dígito de la n'th permutación. –
Sugerencia relacionada: Intente realizar una búsqueda en "base factorial" y "código Lehmer" – Nemo