- 2008年4月 1日 16:54
- しらべる
たとえば、
1,2,4という配列があったとして、これの総当りの順列のリストを出したい。
組み合わせ数が２のときは、[1,2], [1,4], [2,1], [2,4], [4,1], [4,2]
組み合わせ数が３のときは、[1,2,4], [1,4,2], [2,1,4], [2,4,1], [4,1,2], [4,2,1]
という具合。
いくつかの文献を参考にして、こんな風にしたらうまく行ったのでメモ。
/**
* 順列列挙
* @param seed 列挙したい配列
* @param rslt 結果の格納先
* @param pos 0で呼び出し
* @param len 組み合わせの数
*/
function permitation(seed:Array, rslt:Object, pos:Number, len:Number) {
if(pos >= seed.length) {
rslt[seed.join("").substr(0, len)] = seed.join("").substr(0, len); return;
}
permitation(seed, rslt, pos+1, len);
for(var i = pos+1; i < seed.length; ++i) {
var tmp = seed[i];
seed[i] = seed[pos];
seed[pos] =tmp ;
permitation(seed, rslt, pos+1, len);
tmp = seed[i];
seed[i] = seed[pos];
seed[pos] =tmp ;
}
}
var rslt = {};
permitation([1,2,3,4], rslt, 0, 3);
for(var p in rslt){
trace(rslt[p]);
}
上記の結果は
412
413
431
432
421
423
342
341
314
312
324
321
241
243
234
231
214
213
142
143
134
132
124
123
permitation([1,2,3,4], rslt, 0, 2);
とした場合は
41
43
42
34
31
32
24
23
21
14
13
12
重複時に上書きして値をセットしている箇所があるので、たぶんこれよりよい方法もあると思うけど、
要素数と組み合わせ数が一桁ならパフォーマンスはそれほど悪くないので、よしとした。
