Ленивая генерация перестановок

Я ищу алгоритм для генерации перестановок набора таким образом, чтобы я мог сделать их ленивый список в Clojure. т.е. я хотел бы перебрать список перестановок, где каждая перестановка не вычисляется до тех пор, пока я ее не запрошу, и все перестановки не должны храниться в памяти сразу.

В качестве альтернативы я ищу алгоритм, в котором для определенного набора он вернет «следующую» перестановку этого набора таким образом, что многократный вызов функции на ее собственном выходе будет циклически проходить через все перестановки исходного набора в какой-то порядок (какой порядок не имеет значения).

Есть такой алгоритм? Большинство алгоритмов генерации перестановок, которые я видел, имеют тенденцию генерировать их все сразу (обычно рекурсивно), что не масштабируется до очень больших наборов. Была бы полезна реализация на Clojure (или другом функциональном языке), но я могу понять это по псевдокоду.

Да, это алгоритм «следующая перестановка», и это довольно просто слишком. В стандартной библиотеке шаблонов C ++ (STL) даже есть вызываемая функция next_permutation.

Алгоритм фактически находит следующую перестановку - лексикографически следующую. Идея такова: предположим, вам дана последовательность, скажем «32541». Какая следующая перестановка?

Если вы подумаете, то увидите, что это «34125». И ваши мысли, вероятно, были примерно такими: В "32541",

• невозможно сохранить фиксированное число «32» и найти более позднюю перестановку в части «541», потому что эта перестановка уже является последней для 5,4, а 1 - она ​​отсортирована в порядке убывания.
• Таким образом, вам придется заменить «2» на что-то большее - фактически, на наименьшее число, большее, чем в части «541», а именно на 4.
• Теперь, когда вы решили, что перестановка начнется с «34», остальные числа должны быть в порядке возрастания, поэтому ответ будет «34125».

Алгоритм состоит в том, чтобы реализовать именно эту цепочку рассуждений:

1. Найдите самый длинный «хвост» в порядке убывания. (Часть "541".)
2. Измените число непосредственно перед хвостом («2») на наименьшее число, большее, чем в хвосте (4).
3. Отсортируйте хвост в порядке возрастания.

Вы можете выполнить (1.) эффективно, начав с конца и вернувшись назад, если предыдущий элемент не меньше текущего. Вы можете сделать (2.), просто поменяв местами «4» на «2», так что у вас будет «34521». Как только вы это сделаете, вы можете избежать использования алгоритма сортировки для (3.), потому что хвост был и остается (подумайте об этом), отсортированным в порядке убывания, поэтому его нужно только поменять местами.

Код C ++ делает именно это (посмотрите исходный код в /usr/include/c++/4.0.0/bits/stl_algo.hвашей системе или прочтите эту статью ); его должно быть просто перевести на ваш язык: [Прочтите «BidirectionalIterator» как «указатель», если вы не знакомы с итераторами C ++. Код возвращается, falseесли нет следующей перестановки, т.е. мы уже в порядке убывания.]

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;
        }
    }
}

Может показаться, что на перестановку может потребоваться O (n) раз, но если вы подумаете об этом более внимательно, вы можете доказать, что для всех перестановок в целом требуется O (n!) Времени, так что только O (1) - постоянное время - перестановка.

Хорошо то, что алгоритм работает, даже если у вас есть последовательность с повторяющимися элементами: скажем, с «232254421», он найдет хвост как «54421», поменяет местами «2» и «4» (так «232454221» ), переверните остальные, получив "232412245", что является следующей перестановкой.

Предполагая, что мы говорим о лексикографическом порядке переставляемых значений, вы можете использовать два общих подхода:

1. преобразовать одну перестановку элементов в следующую перестановку (как опубликовал ShreevatsaR), или
2. непосредственно вычислить nth перестановку, считая nот 0 вверх.

Для тех (вроде меня ;-), кто не говорит на C ++ как носители языка, подход 1 может быть реализован из следующего псевдокода, предполагающего отсчитываемую от нуля индексацию массива с нулевым индексом «слева» (заменяя некоторую другую структуру , например список, "оставлено как упражнение" ;-):

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

Вот пример, начинающийся с текущей перестановки 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

Для второго подхода (прямое вычисление nth перестановки) помните, что есть N!перестановки Nэлементов. Следовательно, если вы переставляете Nэлементы, первые (N-1)!перестановки должны начинаться с наименьшего элемента, следующие (N-1)!перестановки должны начинаться со второго наименьшего элемента и так далее. Это приводит к следующему рекурсивному подходу (опять же в псевдокоде с нумерацией перестановок и позиций от 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

Так, например, 13-я перестановка ABCD находится следующим образом:

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

Между прочим, «удаление» элементов может быть представлено параллельным массивом логических значений, который указывает, какие элементы все еще доступны, поэтому нет необходимости создавать новый массив при каждом рекурсивном вызове.

Итак, чтобы перебрать перестановки ABCD, просто посчитайте от 0 до 23 (4! -1) и напрямую вычислите соответствующую перестановку.

Вам следует проверить статью о перестановках в Википеде. Также существует понятие факторадических чисел.

В любом случае математическая задача довольно сложная.

В C#вы можете использовать iteratorи остановить использование алгоритма перестановки yield. Проблема в том, что вы не можете перемещаться вперед и назад или использовать index.

Еще примеры алгоритмов перестановки для их генерации.

Источник: http://www.ddj.com/architect/201200326

1. Использует алгоритм Фике, который является одним из самых быстрых из известных.
2. Использует алгоритм лексографического порядка.
3. Использует нелексографический, но работает быстрее, чем пункт 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.

функция перестановок в clojure.contrib.lazy_seqs уже утверждает, что делает именно это.