La clasificación del diccionario genera permutaciones
El algoritmo para generar permutaciones completas es enumerar todas las permutaciones completas posibles para un conjunto de caracteres determinado de manera eficiente sin duplicaciones ni omisiones. Cualquier disposición de n conjuntos de caracteres puede corresponder uno a uno con la disposición de n números del 1 al n. Por lo tanto, la disposición de n números se utiliza como ejemplo para ilustrar el método de generación de la disposición.
Existe una cierta relación de orden lineal entre todas las disposiciones de n caracteres. Todos menos el último acuerdo tienen un sucesor; excepto el primer acuerdo, hay un precursor. El sucesor de cada permutación se puede obtener de su predecesor menos modificado, y el algoritmo que genera todas las permutaciones es un método que genera todas las permutaciones una por una a partir de la primera permutación.
Por lo general, existen los siguientes métodos para generar permutaciones completas:
Método de clasificación por diccionario
Método decimal incremental
Método decimal decreciente
Método de intercambio de posición
Algoritmo recursivo
1. Método de clasificación del diccionario
En el método de clasificación del diccionario, para los números 1, 2, 3 El orden de las diferentes disposiciones se determina comparando el orden de los números correspondientes uno por uno, de izquierda a derecha. Por ejemplo, para las permutaciones de cinco dígitos 12354 y 12345, la permutación 12345 aparece primero y la permutación 12354 aparece al final. Según esta regla, entre los cinco números, el primero es 12345 y el último es 54321.
El algoritmo de orden del diccionario es el siguiente:
Supongamos que p es una permutación completa de 1 ~ n: p = p1p2...pn = p1p2...pj-1ppj+1ppk +65438.
1) Comenzando desde el extremo derecho del arreglo, encuentre el número de serie j del primer número menor que el número de la derecha (j se calcula desde el extremo izquierdo), es decir, j = max {i | pi
2) Entre los números a la derecha de pj, encuentre el número más pequeño pk entre todos los números mayores que pj, es decir, k = max {I | pi》;Pj} ( los números de la derecha aumentan de derecha a izquierda, por lo que k es el número más alto entre todos los números mayores que Pj)
3) Intercambia pi y pk
4) Luego Pj+1 ...PK-1ppk+1pn se invierte para obtener la permutación P”= P 1p 2...Pj-1ppjpn...PK+1ppk-.
Por ejemplo, 839647521 es la permutación de números 1 ~ 9. Los pasos para generar la siguiente permutación a partir de ella son los siguientes:
De derecha a izquierda, encuentra el primer número 4 839647521, que es más pequeño que el número de la derecha
Encuentra el número más pequeño después de este número que sea mayor que 4 5 839647521
p>Intercambia 5 y 4 con 839657421.
Invierte 7421 839651247.
Entonces, la siguiente permutación de 839647521 es 839651247.
2. El método decimal incremental
En el método decimal incremental, se necesita un número intermedio para encontrar una permutación a partir de otra. de dígitos a la derecha del elemento P1 en la permutación p1p2...pi...pn está dado por ki significa que el número del medio de la permutación es la permutación correspondiente K1...Kiwanis International...KN-1
Por ejemplo, el número del medio de la permutación 839647521 es 72642321, y 7, 2, 6,... ¿Son los números a la derecha de los números 8, 3 y 9 más pequeños que ellos?
El número del medio es el enlace intermedio para calcular el acuerdo. Primero, determine el número de intermediarios para el sucesor del acuerdo, el número de intermediario es el número de intermediario del acuerdo original más 1. Cabe señalar que si el último dígito del número del medio es kn-1+1=2, avanzará.
En general, si KI+1 = Por ejemplo, si la intermediación en la permutación 839647521 es 72642321, entonces la intermediación en la siguiente permutación es 6734221+1 = 67342300 (avanzar porque 1+1=2.
Una vez obtenido el número intermedio, se puede restaurar la disposición correspondiente en base a él.
El algoritmo es el siguiente:
Los números intermedios k1, k2,..., kn-1. representa el número N, n-1,...,2 comienzan desde el extremo derecho en el arreglo, por lo que es necesario presionar k1,k2,...,KN y ponerlos uno por uno en el arreglo: I comienza desde la derecha y coloca la posición ki+1. Si ya hay un número colocado, la posición no se cuenta y el último espacio se pone en 1. Por lo tanto, de 67342300 obtenemos la permutación 849617523, que es la última permutación de 839647521. Ponlo primero, k1 = 6, 9 se coloca en la séptima posición desde la derecha, dejando seis espacios, y luego pon 8, k2 = 7, 8 se coloca en la octava posición desde la derecha, pero 9 ocupa una posición, entonces 8 Debe colocarse en el noveno dígito desde la derecha, y así sucesivamente.
3 Método decimal decreciente
En el método decimal incremental, el dígito más bajo del número del medio es. 1 para cada número binario, lo cual es un inconveniente. Invierta el número decimal ascendente para obtener el número decimal descendente 839647521. El número del medio es 6734221 (k 1k 2...KN-1), que se invierte a 1224376 (KN). -1...K2K1). Dada una permutación p, el número medio de la siguiente permutación de p se define como el número medio de p más 1. Por ejemplo, p=839647521, el número de intermediación de p es 1224376 y el número medio de la siguiente permutación de p. El número es 1224376+1 = 12224377, por lo que la siguiente permutación de p es 893647527.
Dado el número intermedio, la permutación se puede recuperar mediante un método similar al método decimal incremental Sin embargo, en el sistema decimal, lo siguiente Se puede obtener una permutación directamente a partir de una permutación sin calcular primero los números intermedios. El algoritmo específico es el siguiente:
1) Si p(I) = n y I
2) Si p. (n) = n, encuentre una secuencia decreciente consecutiva 9, 8,...,I, elimínela del extremo izquierdo del arreglo, agréguela a el extremo derecho del arreglo en orden inverso y luego intercambie i-1 con el número de la izquierda.
Por ejemplo, la siguiente permutación de p=893647521 es 983647521. Al buscar la siguiente permutación de 983647521, debido a que 9 está en el extremo izquierdo, la segunda posición es 8 y la tercera posición no es 7, 8 y 9 se clasifican en el extremo derecho de 364752189, y luego la siguiente permutación de 983647521 es 36745265438+. Por ejemplo, para encontrar la siguiente permutación de 987635421, simplemente ordene 9876 de menor a mayor en el extremo derecho y cambie 5 con el número 3 a la izquierda para obtener 534216789.
4. Método de intercambio de bits positivo
La siguiente permutación en el método de permutación adyacente siempre se obtiene intercambiando algunos dos dígitos adyacentes de la permutación anterior. Tomando como ejemplo la disposición de cuatro elementos, intercambiando el último elemento 4 con los elementos anteriores uno a uno, se pueden generar cuatro nuevas disposiciones:
1 2 3 4 1 2 4 3 1 4 2 3 4 1 2 3
Luego, intercambie los dos elementos al final de la última permutación y luego intercambie el 4 en la parte superior de la fila con los siguientes elementos uno por uno para generar cuatro nuevas permutaciones:
4 1 3 2 1 4 3 2 1 3 4 2 1 3 2 4
Luego intercambie los dos elementos al final de la última permutación y mueva 4 de atrás hacia adelante:
3 1 2 4 3 1 4 2 3 4 1 2 4 3 1 2
Este bucle no solo encuentra todas las permutaciones.
5. Método de incremento de elementos (método de N elementos)
1), comenzando desde la disposición original P = P1p2...PN, agregue n-1 a la enésima posición. Si el valor del bit excede N, divídalo entre N, reemplace el bit con el resto y transpórtelo (enésimo bit más 1).
2) El bit n-1, el bit n-2,... se procesan de la misma manera hasta que ya no se produce el acarreo y se genera una nueva permutación después de procesar una permutación.
3) Eliminar arreglos con los mismos elementos.
4) Cuando el valor del primer elemento es "; n termina"
Tome la disposición de tres números 1, 2 y 3 como ejemplo: la disposición original es 1 ^2^ 3, entonces el tercer elemento es 3, 3+2 = 5, 5 Mod 3 = 2, el segundo elemento es 2, 2+1 = 3, entonces la nueva disposición es 1^3^2. Por incremento de elementos, el orden es: 1 2 3, 1 3 2, 2 1 1, 2 1 3, 2 2 2, 2 3 1, 2 3 3, 3 1 2, 3265438.
Hay elementos repetidos en la disposición subrayada. Deséchalos y lo único que queda es el arreglo.
6. Algoritmo recursivo
La recursión se utiliza para describir de manera concisa el método de generación de reemplazo total, y existen muchos métodos de implementación.
1) Método de retroceso
El método de retroceso generalmente construye un árbol de expansión. Tome tres elementos como ejemplo; los nodos del árbol tienen datos y los valores aceptables son 1, 2 y 3. Si 1 es 0, significa que no hay valor.
El estado inicial es (0, 0, 0) y el valor del primer elemento se puede seleccionar como 1, 2, 3 respectivamente, por lo que se expanden tres nodos secundarios. Utilice el mismo método para encontrar los valores posibles del segundo elemento de estos nodos, y así sucesivamente. Una vez que los tres datos del nuevo nodo no sean cero, se encontrará un esquema de disposición completo. Después de probar todas las soluciones posibles, salió la respuesta al problema.
2) Algoritmo recursivo
Si p representa una permutación de n elementos, Pi representa una permutación sin el elemento I, y (I) Pi representa una permutación con el prefijo I antes de la permutación Pi, entonces la disposición de n elementos se puede definir recursivamente como:
Si n=1, la permutación P tiene solo un elemento I.
Si n & gt1, entonces la permutación p se reemplaza por la permutación (I) Pi (I = 1, 2,...n-1).
Por definición, es fácil ver que si se ha generado una permutación de k-1 elementos, entonces se pueden generar k elementos agregando el elemento I antes de cada permutación Pi de la disposición de k-1 elementos. Por ejemplo, las permutaciones de dos elementos son 1^2 y 2^1, mientras que para el otro elemento, p1 es 2^3 y 3^2. Sumar 1 antes de cada permutación genera dos nuevas permutaciones, 1^2^3 y 1^3^2, siendo p2 y p3 1^3 y 3652. Las nuevas permutaciones 2 1 3, 2 3 1, 3 1 2 y 3 2 1 se pueden generar mediante el mismo método.
3) Método de desplazamiento circular
Si se ha generado una disposición de k-1 elementos, agregue el elemento k después de cada disposición para convertirla en una disposición de k elementos, y luego cada uno. La disposición se mueve hacia la izquierda (derecha) cíclicamente y cada movimiento genera una nueva disposición.
Por ejemplo, las disposiciones de dos elementos son 1^2 y 2^1. Después de 1^2, suma 3 para convertirlo en la nueva permutación 1^2^3 y muévelo circularmente hacia la izquierda para generar la nueva permutación 2^3 1, 3^1^2, de manera similar, 2^1^3, 1 ^ 3^2 y 3^2 1 pueden generar nuevas permutaciones.