Como isso funciona “lexicográfica fim geração algoritmo”?

Question

Wikipedia :

geração de ordem lexicográfica

Para cada número k, com 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;
 }

O que é o lógica por trás disso? Como funciona ??

Answer 1

Imagine que você tem um número inteiro x e você quer saber o que dígito está na posição centenas. (Por exemplo, se x = 4723 você quer a resposta 7.) Para calcular isso, primeiro você dividir por 100, jogando fora a parte fracionária. (Em nosso exemplo, isto deixa 47.) Em seguida, localize o restante quando você dividir por 10.

Agora, suponha que você deseja encontrar o valor do dígito na posição milhares. Para descobrir que você tinha primeira divisão em 1000, jogando fora a parte fracionária, em seguida, novamente encontrar o restante quando você dividir por 10.

No sistema de numeração decimal regular, cada lugar tem um dos 10 valores. Você pode observar que em nosso exercício de apuramento de dígitos que primeiro dividir pelo número de combinações possíveis de valores em locais à direita a que se preocupam com (10 * 10 no primeiro exemplo). Então encontramos o restante quando dividindo pelo número de possíveis valores para o lugar que se preocupam. Claro, todas lugares têm 10 valores possíveis, de modo que basta dividir por 10.

Agora , imagine um sistema de numeração que cada lugar tem um número diferente de valores. Nosso mais à direita lugar pode ter dois valores, 0 ou 1. O próximo lugar pode ter três valores, 0, 1 ou 2; e assim por diante. Neste sistema contamos como esta:

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

Isto é o que wrang-wrang meio de um "número-base de variável".

Agora, você pode ver como podemos calcular o dígito em um lugar neste sistema. Para encontrar o mais à direita não precisamos dividir em primeiro lugar, e nós encontrar o modulo restante 2, porque há 2 valores possíveis para um dígito nessa coluna. Para localizar a próxima coluna à esquerda, primeiro dividir pelo número de combinações possíveis para dígitos nas colunas à direita: só há uma coluna com dois dígitos possíveis, de modo que dividir por 2. Em seguida, tomamos o modulo restante 3, porque existem três possíveis valores para esta coluna. Continuando à esquerda, para a 3ª coluna, dividir por 6 (porque as colunas à direita tem 3 e 2 possibilidades cada, multiplicando para fazer 6) e, em seguida, tomar o modulo restante 4, porque existem 4 valores possíveis nesta coluna.

Vamos dar uma olhada na função:

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

factorial começa como (n-1)!

    for j= 1 to n- 1 {

Cada vez que chegar aqui, factorial é igual a (n-j)! Isso é óbvio, da primeira vez, desde j = 1 e sabemos que inicializado factorial a (n-1)! Veremos mais tarde que factorial é de fato sempre (n-j)!

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

Aqui nós dividir k por factorial (que é igual a (n-j)!) E jogar fora o restante, em seguida, tomamos o manteve quando dividimos o resultado por (n + 1-j). Espere um minuto, tudo o que eu babble começou com está começando a soar familiar! Estamos apenas encontrar o valor do "dígitos" na coluna enésima da esquerda, usando o nosso "sistema de número-base de variável"!

Este próximo bit leva a sequência de elementos entre os índices j e j + tempj e gira-lo para a direita - ou seja, cada elemento se move para cima um índice, exceto a última, que se move de volta para o começo. É importante perceber que todos os números à direita da posição j estão em ordem. Estamos arrancando efetivamente um deles para fora e empurrando o resto ao longo de mantê-los em ordem. Qual deles nós arrancar depende tempj. Quando tempj é 0, nós escolhemos o menor (e realmente não precisa fazer qualquer cutucada), quando tempj é igual a n-j, nós escolhemos o maior.

        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 seguir, (n-j)! dividido por (n-j) dá (n-j-1)! Se você pensar sobre isso, você deve ver que isto significa que quando voltarmos para o topo do loop e j tem incrementado por um, factorial será mais uma vez igual (n-j)!

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

Espero que ajude um pouco!

Answer 2

Pense em um array multi-dimensional, de todas as permutações de n itens, com dimensões:

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

Qualquer array multi-dimensional pode ser linearizada em uma matriz 1d de dimensão:

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

É como um número-base de variável; indo em ordem de valor numérico lhe dá ordem lexicográfica nos dígitos.

O índice usado para se referir a um tuplo x [n] = v.g. (i[n],i[n-1]...,i[0]) é sum_j i[j]*(j!)

Assim, a divisão / mod está se recuperando a próxima posição da tupla.

O valor do índice k na tupla é o produto das dimensões à sua direita, que passa a ser k!.

Answer 3

Say u tem sequência inicial como uma [] = {1,2,3,4,5,6} de n = 6; e u deseja gerar perm k. Com 1 em Ist lugar, u pode gerar 5! (Ou seja, (n-1)!) Permanentes com os lugares restantes.

1 ,.......  

Em seguida, u xchange 1 e 2 e novamente u novamente pode gerar 5! perms.

2 ,.......

Assim, a idéia é dado k, temos de encontrar a extensão de k. O que eu quero dizer é: digamos k é de 225, quantos 5! se k ter: 245/5! = 2 Então, se k = 245, na permutação que eu quero gerar, o primeiro lugar é definitivamente 3 (ou seja, um [2]) (bcoz depois de passar 2 * 5! = 240, vou xchange 1 e 3), terei

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.)

é por isso que no algo, u fazer k / (n-1)! na primeira iteração. E obter restante k = mod k (n-1) !. Este é o novo valor de k e u ir de forma recursiva fazendo a mesma coisa com (n-j)! sobre os locais restantes.