Fórmula de reemplazo completa
1, 3, 2
2, 1, 3
2, 3, 1
3, 2, 1
3, 1, 2
Esto se debe a que el algoritmo solo considera cómo generar el arreglo completo y no considera si hay un problema con la transposición.
Así que propuse una solución, que es modificar la función de transposición.
Si se transpone 1^2^3, no debería ser directamente 3^2^1.
Transpongamos directamente 3 y 1; en su lugar, dejemos que haya 3 líneas delante y detrás, 1^2 introducirá secuencialmente cuatro algoritmos de permutación total:
Ordenación del diccionario
Método decimal incremental
Método decimal decreciente
(d) El método de sustitución de adyacencia especifica la relación de orden de los caracteres en un conjunto de caracteres determinado y especifica dos disposiciones completas sobre esta base. El orden es comparar los caracteres correspondientes uno por uno de izquierda a derecha.
[Ejemplo] Conjunto de caracteres {1, 2, 3}, ingrese primero el número más pequeño.
La disposición total generada según el orden del diccionario es: 123, 132, 213, 231, 312, 321.
[Nota] La disposición completa puede considerarse como una cadena, y la cadena puede tener prefijos y sufijos.
1) Generar la siguiente permutación de la permutación completa dada. El llamado arreglo siguiente significa que no hay nada entre este y el siguiente. Esto requiere que éste y el siguiente tengan el prefijo más largo posible, es decir, los cambios se limitan al sufijo más corto.
[Ejemplo] 839647521 es la disposición del 1 al 9.
En la disposición del 1 al 9, el primero es 123456789 y el último es 987654321. Si el escaneo aumenta de derecha a izquierda, llegará a 987654321 y no habrá siguiente. De lo contrario, busque la ubicación de la primera caída. 1) Encuentre el número del medio mediante permutación. En el método de clasificación del diccionario, el número de dígitos del número del medio está determinado por el número de dígitos del número de permutación. El subíndice del dígito del medio es el mismo que el subíndice del dígito de reemplazo.
En el sistema decimal incremental, el número de dígitos en el medio está determinado por los dígitos en la disposición. Es decir, el subíndice de cada dígito del número del medio es coherente con el número de la disposición (2-n). Podemos ver la cadena de transporte para n-1 bits. En el extremo derecho, cada 1 binario es 1, y en la segunda posición a la derecha, cada 1 ternario es,
El iésimo dígito de la derecha es de i 1 a 1, i=1, 2 ,… n-1. Este número intermedio se llama dígito de acarreo incremental. Los anteriores están ordenados según el número del medio.
Encuentre el número del medio (número decimal creciente) del número de serie (número decimal) de la siguiente manera:
m=m1, 0≤m≤n! -1
m1=2m2 kn-1, 0≤kn-1≤1
m2=3m3 kn-2, 0≤kn-2≤2
………………
Mn-2 = (n-1)Mn-1 k2, 0≤k2≤n-2
mn-1=k1, 0≤ k1 ≤n-1
p 1p 2…pn←→(k 1k 2…kn-1) ↑←→m
En la clasificación de diccionarios, es muy problemático organizar con números intermedios, podemos mejorar definiendo decimales incrementales.
Por conveniencia, supongamos que ai 1=kn-1, i=1, 2,..., n-1.
（k 1 k2…kn-1） ↑=（Anan-1…a2）ⅳ
ai: El número de dígitos en el lado derecho de I es menor que I.
Según esta definición,
tener 839647521←→（6734221）
(67342221) ↑ 1=(67342300) ↑←→849617523
6×8 7)×7 3)×6 4)×5 2)×4 2)×3 2)×2 1 =279905
Encontrar a partir de (anan-1…a2) p1p2 …pn.
Encuentra las posiciones de n, n-1,...,2,1 de mayor a menor.
_ ..._ n _ _ ..._ (un espacio)
Hay un espacio a la derecha de n.
Hay un espacio -1 a la derecha de n-1.
…………
Hay a2 espacios a la derecha de 2.
El último espacio es la posición 1. En el método decimal incremental, el bit más bajo de los números intermedios es 1 para cada número binario, lo cual es una desventaja.
Invierte un número decimal ascendente para obtener un número decimal descendente. (Anan-1…a2) ↑→ (a2a 3…an-1an)↓
839647521→ (12224376)↓
(12224376)↓=1×3 2)×4 2)×5 2)×6 4)×7 3)×8 7)×9 6=340989
【Nota】Es muy fácil encontrar la siguiente permutación. Los números intermedios en el sistema decimal no se acarrean con frecuencia, por lo que es fácil encontrar la siguiente permutación sin acarrear.
Esto nos inspiró, ¿podemos diseñar un algoritmo para que la siguiente permutación siempre se obtenga intercambiando dos números adyacentes de la permutación anterior?
La transposición de números en decimal descendente es unidireccional, de derecha a izquierda, mientras que la transposición de números adyacentes es bidireccional. El algoritmo se puede describir de la siguiente manera:
Para cada permutación par de 1-n-1, inserte n en n espacios (incluidos ambos extremos) de derecha a izquierda para generar n permutaciones de 1-n
p>Para cada permutación impar de 1-n-1, inserte n en n espacios de izquierda a derecha, obteniendo así n permutaciones de 1-n
Para [2, esto es cierto para cada número en n].
839647521
Método de clasificación del diccionario, método de acarreo ascendente, método de acarreo descendente, método de intercambio adyacente
Siguiente 839651247 849617523 893647521 836947521
Intermediario número 72642321 = 6734221 = 1224376↓121372↓
Número de serie 297191 279905 340989 203393