Clojure でそれらの遅延リストを作成できるような方法でセットの順列を生成するアルゴリズムを探しています。つまり、要求するまで各順列が計算されず、すべての順列を一度にメモリに格納する必要がない順列のリストを繰り返し処理したいと考えています。
または、特定のセットが与えられた場合、そのセットの「次の」順列を返すアルゴリズムを探しています。これにより、独自の出力で関数を繰り返し呼び出すと、元のセットのすべての順列が循環します。いくつかの順序 (順序は重要ではありません)。
そのようなアルゴリズムはありますか？私が見た順列生成アルゴリズムのほとんどは、それらをすべて一度に (通常は再帰的に) 生成する傾向があり、非常に大きなセットには拡張できません。Clojure (または別の関数型言語) での実装は役に立ちますが、疑似コードから理解できます。
はい、「次の順列」アルゴリズムがあり、それも非常に単純です。C++ 標準テンプレート ライブラリ (STL) には、 という関数さえありますnext_permutation。
アルゴリズムは実際に次の順列 (辞書順で次の順列) を見つけます。アイデアは次のとおりです。「32541」などのシーケンスが与えられたとします。次の順列は何ですか？
よくよく考えてみると「34125」であることがわかります。そして、あなたの考えはおそらく次のようなものでした：「32541」では、
アルゴリズムは、その推論を正確に実装することです。
(1.) は、前の要素が現在の要素よりも小さくない限り、最後から開始して逆方向に進むことで効率的に実行できます。(2.) "4" を "2" に置き換えるだけで、"34521" が得られます. これを行うと、(3.) のソート アルゴリズムの使用を避けることができます。昔も今も（これについて考えてみてください）、降順でソートされているので、逆にするだけで済みます。
C++ コードはまさにこれを/usr/include/c++/4.0.0/bits/stl_algo.h行います (システムのソースを参照するか、この記事を参照してください)。それを自分の言語に翻訳するのは簡単なはずです。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」を与えます。
置換される値の辞書式順序について話していると仮定すると、使用できる一般的な方法が 2 つあります。
n数えながら th 順列を直接計算します。nネイティブとして C++ を話さない人 (私のように ;-) の場合、アプローチ 1 は次の疑似コードから実装できます。「左」にインデックス 0 を持つ配列のゼロベースのインデックス付けを想定しています (他の構造に置き換えます)。 、リストなどは「練習問題として残します」;-):
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
n2 番目のアプローチ ( th 順列の直接計算) では、要素N!の順列があることに注意してください。Nしたがって、N要素を並べ替える場合、最初の(N-1)!並べ替えは最小の要素から開始し、次の(N-1)!並べ替えは 2 番目に小さい要素から開始する必要があります。これは、次の再帰的アプローチにつながります (これも疑似コードで、順列と位置に 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
したがって、たとえば、ABCD の 13 番目の順列は次のようになります。
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) まで数えて、対応する順列を直接計算します。
それらを生成するための順列アルゴリズムのその他の例。
ソース: http://www.ddj.com/architect/201200326
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の順列関数は、すでにこれを実行すると主張しています。