¿Cómo esta “algoritmo de generación de órdenes de Lexographic” funciona?

Question

Wikipedia :

generación orden lexicográfico

  

Para cada número k, con 0 ≤ k

function permutation(k, s) {
     var int n:= length(s); factorial:= 1;
     for j= 2 to n- 1 {             // compute (n- 1)!
         factorial:= factorial* j;
     }
     for j= 1 to n- 1 {
         tempj:= (k/ factorial) mod (n+ 1- j);
         temps:= s[j+ tempj]
         for i= j+ tempj to j+ 1 step -1 {
             s[i]:= s[i- 1];      // shift the chain right
         }
         s[j]:= temps;
         factorial:= factorial/ (n- j);
     }
     return s;
 }

¿Cuál es el lógica detrás de esto? ¿Cómo funciona ??

Answer 1

Imagine que tiene un x número entero y quiere saber qué dígito está en la posición de las centenas. (Por ejemplo, si x = 4723 desea la respuesta 7.) Para calcular esto, primero se divide por 100, tirando la parte fraccionaria. (En nuestro ejemplo, esto deja a 47.) A continuación, busque el resto cuando se divide por 10.

Ahora supongamos que desea encontrar el valor del dígito en la posición de miles de personas. Para saber que es bastante primera división en 1000, tirando la parte fraccionaria, a continuación, volverá a encontrar el resto cuando se divide por 10.

En el sistema de numeración decimal regular, cada lugar tiene una de 10 valores. Se puede observar que en nuestro ejercicio dígitos de investigación que primero se divide por el número de posibles combinaciones de valores en lugares a la derecha del que nos preocupa (10 * 10 en el primer ejemplo). Entonces nos encontramos con el resto de la división por el número de valores posibles para el lugar que nos importa. Por supuesto, todos lugares tienen 10 valores posibles, por lo que sólo se dividen en 10.

ahora , imaginar un sistema de numeración que cada lugar tiene un número diferente de valores. Nuestro más a la derecha lugar puede tener dos valores, 0 ó 1. El siguiente lugar puede tener tres valores, 0, 1 ó 2; y así. En este sistema se cuenta así:

  0
  1
 10
 11
 20
 21
100
101
110
111
120
121
200
201
210
211
220
...

Esto es lo que significa wrang-wrang por un "número-base variable".

Ahora, se puede ver cómo se calcula el dígito en un lugar en este sistema. Para encontrar más a la derecha que no necesitamos para dividir primero, y nos encontramos con el resto módulo 2, porque hay 2 valores posibles de un dígito en esa columna. Para buscar la siguiente columna a la izquierda, primero se divide por el número de posibles combinaciones de dígitos en las columnas de la derecha: sólo hay una columna con dos dígitos posibles, por lo que se divide por 2. Luego tomamos el módulo restante 3, porque hay tres valores posibles para esta columna. Continuando con la izquierda, por la tercera columna se divide por 6 (porque las columnas a la derecha tienen 3 y 2 posibilidades cada uno, multiplicando para hacer 6) y luego tomar el módulo restante 4, porque hay 4 posibles valores de esta columna.

Vamos a echar un vistazo a la función:

function permutation(k, s) {
    var int n:= length(s); factorial:= 1;
    for j= 2 to n- 1 {             // compute (n- 1)!
        factorial:= factorial* j;
    }

factorial comienza como (n-1)!

    for j= 1 to n- 1 {

Cada vez que hemos llegado hasta aquí, factorial es igual a (n-j)! Esto es obvio el primer tiempo de ida, ya que j = 1 y sabemos que hemos inicializado factorial a (n-1)! Veremos más adelante que factorial es de hecho siempre (n-j)!

        tempj:= (k/ factorial) mod (n+ 1- j);

A continuación dividimos k por factorial (que es igual a (n-j)!) Y tirar el resto, entonces tomamos la mantuvo cuando dividimos el resultado por (n + 1-j). Espera un minuto, todo lo que balbuceo Empecé con empieza a sonar familiar! Sólo estamos encontrando el valor de la "dígitos" en la columna izquierda de la enésima utilizando nuestro "sistema de numeración de base-variable"!

Este bit siguiente toma la secuencia de elementos entre los índices j y j + tempj y lo gira hacia la derecha - es decir, cada elemento se mueve hacia arriba un índice, excepto la última, que se mueve de nuevo al comienzo. Es importante darse cuenta de que todos los números de la derecha de la posición j están en orden. Estamos arrancando con eficacia a uno de ellos y empujando el resto a lo largo de mantenerlos en orden. El futuro que nos arrancamos depende de tempj. Cuando tempj es 0, tomamos la más pequeña (y en realidad no es necesario hacer ningún empuje), cuando tempj es igual a n-j, elegimos el más grande.

        temps:= s[j+ tempj]
        for i= j+ tempj to j+ 1 step -1 {
            s[i]:= s[i- 1];      // shift the chain right
        }
        s[j]:= temps;

A continuación, (n-j)! dividido por (n-j) da (n-j-1)! Si se piensa en ello, usted debe ver que esto significa que cuando volvamos a la parte superior del bucle y j ha incrementado en uno, factorial, una vez más igual (n-j)!

        factorial:= factorial/ (n- j);
    }
    return s;
}

Espero que ayude un poco!

Answer 2

Piense en una matriz multi-dimensional, de todas las permutaciones de n elementos, con dimensiones:

p[n][n-1][n-2]...[1]

Cualquier matriz multi-dimensional puede ser linealizado en una matriz de 1d de dimensión:

a[n*(n-1)*(n-2)*...*1]

Es como un número de base de la variable; va por orden de valor numérico te da orden lexicográfico de los dígitos.

El índice que se utiliza para referirse a una tupla x [n] = por ejemplo, (i[n],i[n-1]...,i[0]) se sum_j i[j]*(j!)

Por lo tanto, la división / mod está recuperando la siguiente posición de la tupla.

El valor del índice k-ésimo en la tupla es el producto de las dimensiones a su derecha, que pasa a ser k!.

Answer 3

Say u tienen secuencia inicial como a [] = {1,2,3,4,5,6} de n = 6; y U quiere generar la ondulación permanente de orden k. Con 1 en Ist lugar, u puede generar 5! (Es decir, (n-1)!) Ondulaciones permanentes con los lugares restantes.

1 ,.......  

Entonces u Xchange 1 y 2 y otra vez u otra vez puede generar 5! ondulaciones permanentes.

2 ,.......

Así que la idea es dado k, tenemos que encontrar la medida de k. Lo que quiero decir es: decir k es 225, el número 5! Qué tienen k: 245/5! = 2 Así que si k = 245, en la permutación que yo quiero generar, el primer lugar es, sin duda 3 (es decir, un [2]) (bcoz después de ir 2 * 5! = 240, voy a XCHANGE 1 y 3), tendré

3,1,2,4,5,6 (the array a[] obtained after shifting the chain)
(why we are shifting is to make the remaining array sorted for the 
  next iteration so that lexicographic order is maintained.)

Es por eso que en el algo, u no K / (n-1)! en la primera iteración. Y obtener resto k = k mod (n-1) !. Esto es nuevo valor de k y de forma recursiva u ir haciendo lo mismo con (n-j)! en los puestos restantes.