Gerando permutações preguiçosamente

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.

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.

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.

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.

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.

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