Генерация перестановок лениво

Question

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

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

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

Answer 1

Да, есть алгоритм "следующей перестановки", и он тоже довольно прост. Стандартная библиотека шаблонов 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", что является следующей перестановкой.

Answer 2

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

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

Для тех (как я;-), которые не говорят на С ++ как нативные, подход 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

Для второго подхода (прямого вычисления nпомните, что есть 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) и непосредственно вычислите соответствующую перестановку.

Answer 3

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

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

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

Answer 4

Больше примеров алгоритмов перестановки для их генерации.

Источник: 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.

Answer 5

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

Answer 6

Это выглядит некромантически в 2022 году, но я все равно делюсь этим

Здесь реализация С++next_permutationв Java можно найти. Идея использования его в Clojure может быть чем-то вроде

      (println (lazy-seq (iterator-seq (NextPermutationIterator. (list 'a 'b 'c)))))

отказ от ответственности: я являюсь автором и сопровождающим проекта