Gerando permutações preguiçosamente

87

Estou procurando um algoritmo para gerar permutações de um conjunto de forma que eu possa fazer uma lista preguiçosa deles em Clojure. ou seja, eu gostaria de iterar sobre uma lista de permutações onde cada permutação não é calculada até que eu solicite, e todas as permutações não precisam ser armazenadas na memória de uma vez.

Como alternativa, estou procurando um algoritmo em que, dado um determinado conjunto, ele retornará a "próxima" permutação desse conjunto, de forma que chamar repetidamente a função em sua própria saída percorrerá todas as permutações do conjunto original, em alguma ordem (não importa qual seja a ordem).

Existe tal algoritmo? A maioria dos algoritmos de geração de permutação que vi tendem a gerá-los todos de uma vez (geralmente recursivamente), o que não é escalável para conjuntos muito grandes. Uma implementação em Clojure (ou outra linguagem funcional) seria útil, mas posso descobrir a partir do pseudocódigo.

Brian Carper
fonte

Respostas:

139

Sim, há é um algoritmo de "próxima permutação", e é bastante simples também. A biblioteca de modelos padrão C ++ (STL) tem até uma função chamada next_permutation.

O algoritmo realmente encontra a próxima permutação - a próxima lexicograficamente. A ideia é esta: suponha que você receba uma sequência, diga "32541". Qual é a próxima permutação?

Se você pensar bem, verá que é "34125". E seus pensamentos provavelmente eram algo assim: em "32541",

  • não há como manter o "32" fixo e encontrar uma permutação posterior na parte "541", porque essa permutação já é a última para 5,4, e 1 - é classificada em ordem decrescente.
  • Portanto, você terá que alterar o "2" para algo maior - na verdade, para o menor número maior do que na parte "541", ou seja, 4.
  • Agora, depois de decidir que a permutação começará como "34", o restante dos números deve estar em ordem crescente, portanto, a resposta é "34125".

O algoritmo deve implementar precisamente essa linha de raciocínio:

  1. Encontre a "cauda" mais longa ordenada em ordem decrescente. (A parte "541".)
  2. Altere o número imediatamente antes da cauda (o "2") para o menor número maior que ele na cauda (o 4).
  3. Organize a cauda em ordem crescente.

Você pode fazer (1.) de forma eficiente, começando no final e indo para trás, desde que o elemento anterior não seja menor que o elemento atual. Você pode fazer (2.) apenas trocando o "4" pelo '2 ", então você terá" 34521 ". Depois de fazer isso, você pode evitar o uso de um algoritmo de classificação para (3.), porque a cauda foi, e ainda é (pense nisso), classificado em ordem decrescente, então só precisa ser revertido.

O código C ++ faz exatamente isso (observe o código-fonte em /usr/include/c++/4.0.0/bits/stl_algo.hseu sistema ou consulte este artigo ); deve ser simples traduzi-lo para o seu idioma: [Leia "BidirectionalIterator" como "ponteiro", se você não estiver familiarizado com iteradores C ++. O código retorna falsese não houver próxima permutação, ou seja, já estamos em ordem decrescente.]

template <class BidirectionalIterator>
bool next_permutation(BidirectionalIterator first,
                      BidirectionalIterator last) {
    if (first == last) return false;
    BidirectionalIterator i = first;
    ++i;
    if (i == last) return false;
    i = last;
    --i;
    for(;;) {
        BidirectionalIterator ii = i--;
        if (*i <*ii) {
            BidirectionalIterator j = last;
            while (!(*i <*--j));
            iter_swap(i, j);
            reverse(ii, last);
            return true;
        }
        if (i == first) {
            reverse(first, last);
            return false;
        }
    }
}

Pode parecer que pode levar O (n) tempo por permutação, mas se você pensar mais cuidadosamente, pode provar que leva O (n!) Tempo para todas as permutações no total, então apenas O (1) - tempo constante - por permutação.

O bom é que o algoritmo funciona mesmo quando você tem uma sequência com elementos repetidos: com, digamos, "232254421", ele encontraria a cauda como "54421", troque o "2" e "4" (então "232454221" ), inverta o resto, dando "232412245", que é a próxima permutação.

ShreevatsaR
fonte
2
Isso funcionará, supondo que você tenha um pedido total dos elementos.
Chris Conway
10
Se você começar com um conjunto, poderá definir arbitrariamente uma ordem total dos elementos; mapeie os elementos para números distintos. :-)
ShreevatsaR
3
Esta resposta não consegue votos positivos suficientes, mas só posso votar a favor uma vez ... :-)
Daniel C. Sobral
1
@Masse: Não exatamente ... aproximadamente, você pode ir de 1 a um número maior. Usando o exemplo: Comece com 32541. A cauda é 541. Depois de fazer as etapas necessárias, a próxima permutação é 34125. Agora a cauda é apenas 5. Incrementando 3412 usando o 5 e trocando, a próxima permutação é 34152. Agora a cauda é 52, de comprimento 2. Em seguida, torna-se 34215 (comprimento de cauda 1), 34251 (comprimento de cauda 2), 34512 (comprimento 1), 34521 (comprimento 3), 35124 (comprimento 1), etc. Você está certo de que a cauda é pequeno na maioria das vezes, é por isso que o algoritmo tem bom desempenho em várias chamadas.
ShreevatsaR
1
@SamStoelinga: Você está certo, na verdade. O (n log n) é O (log n!). Eu deveria ter dito O (n!).
ShreevatsaR
42

Supondo que estejamos falando sobre ordem lexicográfica sobre os valores que estão sendo permutados, existem duas abordagens gerais que você pode usar:

  1. transformar uma permutação dos elementos para a próxima permutação (como ShreevatsaR postou), ou
  2. calcular diretamente a nésima permutação, enquanto conta nde 0 para cima.

Para aqueles (como eu ;-) que não falam c ++ como nativos, a abordagem 1 pode ser implementada a partir do seguinte pseudocódigo, assumindo a indexação baseada em zero de uma matriz com índice zero à "esquerda" (substituindo alguma outra estrutura , como uma lista, é "deixado como um exercício" ;-):

1. scan the array from right-to-left (indices descending from N-1 to 0)
1.1. if the current element is less than its right-hand neighbor,
     call the current element the pivot,
     and stop scanning
1.2. if the left end is reached without finding a pivot,
     reverse the array and return
     (the permutation was the lexicographically last, so its time to start over)
2. scan the array from right-to-left again,
   to find the rightmost element larger than the pivot
   (call that one the successor)
3. swap the pivot and the successor
4. reverse the portion of the array to the right of where the pivot was found
5. return

Aqui está um exemplo começando com uma permutação atual de CADB:

1. scanning from the right finds A as the pivot in position 1
2. scanning again finds B as the successor in position 3
3. swapping pivot and successor gives CBDA
4. reversing everything following position 1 (i.e. positions 2..3) gives CBAD
5. CBAD is the next permutation after CADB

Para a segunda abordagem (cálculo direto da nésima permutação), lembre-se de que existem N!permutações de Nelementos. Portanto, se você estiver permutando Nelementos, as primeiras (N-1)!permutações devem começar com o menor elemento, as próximas (N-1)!permutações devem começar com o segundo menor e assim por diante. Isso leva à seguinte abordagem recursiva (novamente em pseudocódigo, numerando as permutações e posições de 0):

To find permutation x of array A, where A has N elements:
0. if A has one element, return it
1. set p to ( x / (N-1)! ) mod N
2. the desired permutation will be A[p] followed by
   permutation ( x mod (N-1)! )
   of the elements remaining in A after position p is removed

Assim, por exemplo, a 13ª permutação de ABCD é encontrada da seguinte forma:

perm 13 of ABCD: {p = (13 / 3!) mod 4 = (13 / 6) mod 4 = 2; ABCD[2] = C}
C followed by perm 1 of ABD {because 13 mod 3! = 13 mod 6 = 1}
  perm 1 of ABD: {p = (1 / 2!) mod 3 = (1 / 2) mod 2 = 0; ABD[0] = A}
  A followed by perm 1 of BD {because 1 mod 2! = 1 mod 2 = 1}
    perm 1 of BD: {p = (1 / 1!) mod 2 = (1 / 1) mod 2 = 1; BD[1] = D}
    D followed by perm 0 of B {because 1 mod 1! = 1 mod 1 = 0}
      B (because there's only one element)
    DB
  ADB
CADB

A propósito, a "remoção" de elementos pode ser representada por um array paralelo de booleanos que indica quais elementos ainda estão disponíveis, portanto, não é necessário criar um novo array a cada chamada recursiva.

Portanto, para iterar pelas permutações de ABCD, basta contar de 0 a 23 (4! -1) e calcular diretamente a permutação correspondente.

joel.neely
fonte
1
++ Sua resposta é subestimada. Para não tirar da resposta aceita, mas a segunda abordagem é mais poderosa porque pode ser generalizada para combinações também. Uma discussão completa mostraria a função reversa da sequência ao índice.
Morrer em Sente de
1
De fato. Concordo com o comentário anterior - embora minha resposta faça um pouco menos operações para a pergunta específica feita, essa abordagem é mais geral, pois funciona para, por exemplo, encontrar a permutação que está a K passos de uma determinada.
ShreevatsaR
4

Você deve verificar o artigo sobre Permutações no wikipeda. Além disso, existe o conceito de números Factoradic .

De qualquer forma, o problema matemático é bastante difícil.

Em C#você pode usar um iterator, e parar o algoritmo de permutação usando yield. O problema com isso é que você não pode ir e voltar ou usar um index.

Bogdan Maxim
fonte
5
"De qualquer forma, o problema matemático é bastante difícil." Não, não é :-)
ShreevatsaR
Bem, é ... se você não conhece os números Factoradic, não há como criar um algoritmo adequado em um tempo aceitável. É como tentar resolver uma equação de 4º grau sem conhecer o método.
Bogdan Maxim
1
Desculpe, pensei que você estava falando sobre o problema original. Ainda não vejo por que você precisa de "Números fatorádicos" de qualquer maneira ... é muito simples atribuir um número a cada um dos n! permutações de um determinado conjunto e construir uma permutação a partir de um número. [Apenas um pouco de programação / contagem dinâmica.]
ShreevatsaR
1
Em C # idiomático, um iterador é mais corretamente referido como um enumerador .
Drew Noakes em
@ShreevatsaR: Como você faria isso sem gerar todas as permutações? Por exemplo, se você precisar gerar a n! Ésima permutação.
Jacob,
3

Mais exemplos de algoritmos de permutação para gerá-los.

Fonte: http://www.ddj.com/architect/201200326

  1. Utiliza o Algoritmo de Fike, que é o mais rápido conhecido.
  2. Utiliza o Algol para o pedido Lexográfico.
  3. Usa o não-flexográfico, mas funciona mais rápido que o item 2.

1


PROGRAM TestFikePerm;
CONST marksize = 5;
VAR
    marks : ARRAY [1..marksize] OF INTEGER;
    ii : INTEGER;
    permcount : INTEGER;

PROCEDURE WriteArray;
VAR i : INTEGER;
BEGIN
FOR i := 1 TO marksize
DO Write ;
WriteLn;
permcount := permcount + 1;
END;

PROCEDURE FikePerm ;
{Outputs permutations in nonlexicographic order.  This is Fike.s algorithm}
{ with tuning by J.S. Rohl.  The array marks[1..marksizn] is global.  The   }
{ procedure WriteArray is global and displays the results.  This must be}
{ evoked with FikePerm(2) in the calling procedure.}
VAR
    dn, dk, temp : INTEGER;
BEGIN
IF 
THEN BEGIN { swap the pair }
    WriteArray;
    temp :=marks[marksize];
    FOR dn :=  DOWNTO 1
    DO BEGIN
        marks[marksize] := marks[dn];
        marks [dn] := temp;
        WriteArray;
        marks[dn] := marks[marksize]
        END;
    marks[marksize] := temp;
    END {of bottom level sequence }
ELSE BEGIN
    FikePerm;
    temp := marks[k];
    FOR dk :=  DOWNTO 1
    DO BEGIN
        marks[k] := marks[dk];
        marks[dk][ := temp;
        FikePerm;
        marks[dk] := marks[k];
        END; { of loop on dk }
    marks[k] := temp;l
    END { of sequence for other levels }
END; { of FikePerm procedure }

BEGIN { Main }
FOR ii := 1 TO marksize
DO marks[ii] := ii;
permcount := 0;
WriteLn ;
WrieLn;
FikePerm ; { It always starts with 2 }
WriteLn ;
ReadLn;
END.

2


PROGRAM TestLexPerms;
CONST marksize = 5;
VAR
    marks : ARRAY [1..marksize] OF INTEGER;
    ii : INTEGER;
    permcount : INTEGER;

PROCEDURE WriteArray; VAR i : INTEGER; BEGIN FOR i := 1 TO marksize DO Write ; permcount := permcount + 1; WriteLn; END;

PROCEDURE LexPerm ; { Outputs permutations in lexicographic order. The array marks is global } { and has n or fewer marks. The procedure WriteArray () is global and } { displays the results. } VAR work : INTEGER: mp, hlen, i : INTEGER; BEGIN IF THEN BEGIN { Swap the pair } work := marks[1]; marks[1] := marks[2]; marks[2] := work; WriteArray ; END ELSE BEGIN FOR mp := DOWNTO 1 DO BEGIN LexPerm<>; hlen := DIV 2; FOR i := 1 TO hlen DO BEGIN { Another swap } work := marks[i]; marks[i] := marks[n - i]; marks[n - i] := work END; work := marks[n]; { More swapping } marks[n[ := marks[mp]; marks[mp] := work; WriteArray; END; LexPerm<> END; END;

BEGIN { Main } FOR ii := 1 TO marksize DO marks[ii] := ii; permcount := 1; { The starting position is permutation } WriteLn < Starting position: >; WriteLn LexPerm ; WriteLn < PermCount is , permcount>; ReadLn; END.

3 -


PROGRAM TestAllPerms;
CONST marksize = 5;
VAR
    marks : ARRAY [1..marksize] of INTEGER;
    ii : INTEGER;
    permcount : INTEGER;

PROCEDURE WriteArray; VAR i : INTEGER; BEGIN FOR i := 1 TO marksize DO Write ; WriteLn; permcount := permcount + 1; END;

PROCEDURE AllPerm (n : INTEGER); { Outputs permutations in nonlexicographic order. The array marks is } { global and has n or few marks. The procedure WriteArray is global and } { displays the results. } VAR work : INTEGER; mp, swaptemp : INTEGER; BEGIN IF THEN BEGIN { Swap the pair } work := marks[1]; marks[1] := marks[2]; marks[2] := work; WriteArray; END ELSE BEGIN FOR mp := DOWNTO 1 DO BEGIN ALLPerm<< n - 1>>; IF > THEN swaptemp := 1 ELSE swaptemp := mp; work := marks[n]; marks[n] := marks[swaptemp}; marks[swaptemp} := work; WriteArray; AllPerm< n-1 >; END; END;

BEGIN { Main } FOR ii := 1 TO marksize DO marks[ii] := ii permcount :=1; WriteLn < Starting position; >; WriteLn; Allperm < marksize>; WriteLn < Perm count is , permcount>; ReadLn; END.

Carlos Eduardo Olivieri
fonte
2

a função de permutações em clojure.contrib.lazy_seqs já afirma fazer exatamente isso.


fonte
Obrigado, eu não estava ciente disso. Ele alega ser preguiçoso, mas infelizmente tem um desempenho muito ruim e transborda facilmente.
Brian Carper
A preguiça pode certamente causar estouros de pilha conforme explicado, por exemplo, nesta resposta.
crockeea