JavaScriptで順列と組み合わせ

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! = 4*3*2*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 ] ] 

これも不器用なので簡略かできるか模索中