トンプキンス・ペイジアルゴリズム
トンプキンス-ペイジアルゴリズム[ 1 ]は、有限のオブジェクト集合の すべての順列を生成するコンピュータアルゴリズムである。
方法
Pとcを長さnの配列とし、1 から始まるインデックス（つまり、配列の最初の要素のインデックスは 1 です）を持つものとします。集合 {1, 2, ..., n } のすべてのn ! 順列を生成するアルゴリズムは、次の擬似コードで与えられます。
P ← [1, 2, ..., n];P を生成します。c ← [*, 1, ..., 1]; ( cの最初のエントリは使用されません) i ← 2; i ≤ nの間、 Pの 最初のiエントリを左回転します。 （例えば、最初の4つのエントリを左に回転させる [4, 2, 5, 3, 1]は[2, 5, 3, 4, 1]になります。 c [ i ] < i の場合、c [ i ] ← c [ i ] + 1; i ← 2;P を返します; そうでなければc [ i ] ← 1; i ← i +1;
上記の擬似コードにおいて、「yield P 」という文は、並べ替えられたインデックスPのセットを出力または記録することを意味します。アルゴリズムが正しく実装されていれば、P は正確にn ! 回生成され、それぞれ異なる並べ替えられたインデックスのセットを持ちます。
このアルゴリズムは、既存の順列生成法の中で最も効率的なものではありません。[ 2 ]補助的な計数配列 ( c )を追跡する必要があるだけでなく、生成の過程で冗長な順列も生成され無視されます ( c [ i ] ≥ iの場合、左回転後にPが生成されないため)。たとえば、n = 4 の場合、アルゴリズムは最初にP = [1,2,3,4] を生成し、次に 40 回の反復で他の 23 個の順列を生成します (つまり、17 回の反復では冗長な順列があり、Pは生成されません)。以下は、生成順にPの 41 個の値すべてをリストしたものです。括弧で囲まれた値は冗長です。
P = 1234 c = *111 i=2 P = 2134 c = *211 i=2 P = (1234) c = *111 i=3 P = 2314 c = *121 i=2 P = 3214 c = *221 i=2 P = (2314) c = *121 i=3 P = 3124 c = *131 i=2 P = 1324 c = *231 i=2 P = (3124) c = *131 i=3 P = (1234) c = *111 i=4 P = 2341 c = *112 i=2 P = 3241 c = *212 i=2 P = (2341) c = *112 i=3 P = 3421 c = *122 i=2 P = 4321 c = *222 i=2 P = (3421) c = *122 i=3 P = 4231 c = *132 i=2 P = 2431 c = *232 i=2 P = (4231) c = *132 i=3 P = (2341) c = *112 i=4 P = 3412 c = *113 i=2 P = 4312 c = *213 i=2 P = (3412) c = *113 i=3 P = 4132 c = *123 i=2 P = 1432 c = *223 i=2 P = (4132) c = *123 i=3 P = 1342 c = *133 i=2 P = 3142 c = *233 i=2 P = (1342) c = *133 i=3 P = (3412) c = *113 i=4 P = 4123 c = *114 i=2 P = 1423 c = *214 i=2 P = (4123) c = *114 i=3 P = 1243 c = *124 i=2 P = 2143 c = *224 i=2 P = (1243) c = *124 i=3 P = 2413 c = *134 i=2 P = 4213 c = *234 i=2 P = (2413) c = *134 i=3 P = (4123) c = *114 i=4 P = (1234) c = *111 i=5
参考文献
- ^ Tompkins, C. (1956). 「変数が順列である問題に対する機械攻撃」. Proc. Symposium in Appl. Math., Numerical Analysis . Vol. 6. McGraw–Hill, Inc., NY. pp. 195– 211.
- ^セジウィック、ロバート(1977). 「順列生成法」 .コンピューティングサーベイ. 9 (2): 137– 164. doi : 10.1145/356689.356692 .
