6
8

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

JavaScriptで順列と組み合わせ

Last updated at Posted at 2018-11-10

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 ] ] 

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

6
8
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
6
8

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?