全順列は、時間計算量が O(n!) のアルゴリズムです。2 日前に学生に講義をしていたときに、偶然この問題を思いつき、7 つのアルゴリズムで解くことができました。このうち動的ループはバックトラッキング アルゴリズムに似ており、実装が比較的面倒なので、読者の便宜のために 6 つのタイプをまとめました。すべてのアルゴリズムは JavaScript で記述されており、直接実行できます。
アルゴリズム 1: 交換 (再帰)
完全置換(再帰的スワップ)
Mengliao Software Studio - Bosun Network Co., Ltd.
2011.05.24
完全順列(再帰リンク)
Mengliao Software Studio - Bosun Network Co., Ltd.
2012.03.29
完全順列(再帰的バックトラック)
Mengliao Software Studio - Bosun Network Co., Ltd.
2012.03.29
2012.03.29
完全な置換 (非再帰モジュロ)
2 の要素の総数を計算します。すべての n 個の要素、つまり n!; 任意の整数 >=0 から開始して n! 回ループし、インデックス
として記録します。 、1 桁の式の最下位ビットを見つけます。つまり、1 を法とするインデックスの値 w を見つけ、結果の最初の要素 (arr[0]) w 位置を挿入し、インデックスを
5 まで繰り返します。 2 番目の要素 arr[1] を取得し、バイナリ式の最下位ビット、つまりインデックス モジュロ 2 の値 w を見つけ、2 番目の要素 (arr[1]) を変更します。結果の w 位置を挿入します。インデックスをインデックス 2 に繰り返します。
6. 3 番目の要素 arr[2] を取得し、3 項式の最下位ビットを見つけます。つまり、インデックス モジュロ 3 w の値を見つけ、3 番目の要素 (arr[2]) を挿入します。結果の w 位置にインデックスをインデックス 3;
7,...
8 まで繰り返し、最後の要素 arr[arr.length-1 が取得される] まで、この時点で順列が得られます。
9. インデックスループが完了すると、すべての順列が取得されます。
例:
4 つの要素 ["a"、"b"、"c"、"d"] の完全な配置を見つけます。ループ 4!= 合計 24 回、任意の位置から開始できます> ;= 整数インデックス 0 によってループが開始され、ループがインデックス 23 に達した後に終了するまで、毎回 1 が累積されます。
インデックス = 13 (または 13 24, 13 2*24, 13 3*24...) と仮定します。 )、合計 4 つの要素があるため、4 回反復後の結果の置換プロセスは次のようになります:
最初の反復、13/1、商 = 13、剰余 = 0、したがって、最初の要素が0 番目の位置 (つまり、添字は 0)、get ["a"];
2 番目の反復、13/2、商=6、剰余=1 なので、2 番目の要素が最初の位置に挿入されます (つまり、つまり、添字は 1) で、[ "a", "b"] が得られます。
3 回目の反復、6/3、商 = 2、剰余 = 0 なので、3 番目の要素が 0 番目の位置に挿入されます。 (つまり、添字は 0)、[" c", "a", "b"] を取得します。
4 回目の反復、2/4、商 = 0、剰余 = 2、つまり 4 番目の要素が 2 番目の位置に挿入されます (つまり、添字は 2 です)。 Get ["c", "a", "d", "b"]; >function show(arr) {
document.write("P" count ": " arr "
");
function perm( arr) {
var result = new Array(arr.length) ;
var fac = 1;
for (var i = 2; i fac * = i;
for (インデックス = 0; インデックス
for (i = 1; i var w = t % i;
for (j = i - 1; j > w; j--)
result[j] = result[j - 1]; = arr[i - 1];
t = Math.floor (t / i);
}
}
perm([" e1", "e2", "e3", "e4"]);
上記の 6 つのアルゴリズムの中には、バックトラッキング、ソートなどの位置を配置するものもあります。これは、配置する要素が数字や文字などである必要はなく、さまざまなタイプの要素に適応できるためです。