JavaScriptで順列と組み合わせをつくる
JavaScriptで[1,2,3]の順列と組み合わせを作ろうと思ったら、いろいろ悩んだのでメモ
rubyだとメソッドがあるがJavaScriptにはない。探せばあるのかな
rubyだと順列はarray.permutation().to_a
、組み合わせはarray.combination().to_a
array = [1, 2, 3]
p array.permutation(3).to_a
# [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
p array.combination(2).to_a
# [[1, 2], [1, 3], [2, 3]]
おさらい
高校の数学がなつかしい
!は階乗の意味
4! = 432*1
順列
nPk = n! / (n - k)!
組み合わせ
nNk = n! / n(n - k)!
順列のアルゴリズム
stabuckyさんのブログを参考させていただきました
https://stabucky.com/wp/archives/5334
おおまかにこんなかんじsplice()で一つずらしつつ、一つ減らした配列を作成
let array1,array2,array3,i,j,k;
let arrayInit = []
//i = 0の処理
array1 = [1, 2, 3] //この配列の順列を出力
//↓
array1 // [1, 2, 3] i = 0
array2.splice(i,1) // array2は[2,3]
//↓
array1 // [1, 2, 3] i = 0
array2 // [2, 3] j = 0
array3.splice(j,1) // [3] k = 0
//↓
array1 // [1, 2, 3] i = 0
array2 // [2, 3] j = 1
array3.splice(j,1) // [2] k = 0
//これをからの配列にpushする
arrayInit.push([array1[0]].concat([array2[0]]).concat([array3[0]]))
arrayInit.push([array1[0]].concat([array2[1]]).concat([array3[0]]))
//こんな感じのfor処理でつくる
let array1 = [1,2,3];
let arrayInit = [];
let i, j, k,array2,array3;
for(i = 0;i < array1.length; i++){
array2 = array1.slice(0)
array2.splice(i, 1);
for(j = 0; j < array2.length; j++) {
array3 = array2.slice(0)
array3.splice(j, 1)
for(k = 0;k < array3.length; k++){
arrayInit.push([array1[i]].concat([array2[j]]).concat([array3[k]]))
}
}
}
console.log(arrayInit)
/*
[ [ 1, 2, 3 ],
[ 1, 3, 2 ],
[ 2, 1, 3 ],
[ 2, 3, 1 ],
[ 3, 1, 2 ],
[ 3, 2, 1 ] ]
*/
おなじ処理を複数しているだけなので、関数処理ができないか模索中
組み合わせ
[1, 2, 3]の2つの組み合わせを考えてみる
簡単に言うと、左端の値から左から一つ減らした配列を組み合わせる
[1]のときは[2,3]の組み合わせ
[2]のときは[3]
let array1,array2,i,j;
let arrayInit = []
//i = 0の処理
array1 = [1, 2, 3] //この2つの組み合わせを出力
//↓
array1 // [1, 2, 3] i = 0
array2.slice(i + 1) // array2は[2,3]
//↓
array1 // [1, 2, 3] i = 1
array2.slice(i + 1) // array2は[3]
//これをからの配列にpushする
arrayInit.push([array1[0]].concat([array2[0]])))
arrayInit.push([array1[0]].concat([array2[1]])))
//こんな感じのfor処理でつくる
let array1 = [1,2,3];
let arrayInit = [];
let i, j,array2;
for(i = 0;i < array1.length; i++){
array2 = array1.slice(i + 1)
for(j = 0; j < array2.length; j++) {
arrayInit.push([array1[i]].concat([array2[j]]))
}
}
console.log(arrayInit)
// [ [ 1, 2 ], [ 1, 3 ], [ 2, 3 ] ]
これも不器用なので簡略かできるか模索中