気が向いたので追記分(8/27)
- combinationしか書いてませんでしたが、permutationも追記
- 関数のベース部分を共通化し、高階関数として書き直したverも追記
この記事について
背景
なんとなく、JSを関数型っぽく書くのにハマっている時期がありまして。
普段はネットとかで拾ってきたコードを簡単に書き直して使うことが多かったりするのですが、必要に駆られて関数型"っぽく" 順列・組み合わせを全探索するコードを書くことがあったので、備忘的に載せておこうと思います。
ここで言う順列・組み合わせとは？
高校数学で習う順列とか組み合わせのこと。
パターンの個数を求めるとき、下の式で表せる奴らです（n, mは自然数, n >= m）。
_nP_m = n (n-1) (n-2)…(n-m+1)
_nC_m = \frac{n(n-1)(n-2)…(n-m+1)}{m(m-1)(m-2)…2・1}
やったこと
配列から任意の個数の要素を抜き出して配列を作るとき、
全てのパターンを要素として持つ配列を返す関数を、「関数型っぽく」作りました。
出来上がり
割と簡潔に書けたんじゃないかと思います。
タイトル詐欺的ですが、コードは組み合わせしかありません。sliceの部分を少し改造したらいいだけですし、まぁいいかな、と。欲しいって人がいたら書くかも。（Dartでは書いてみた）
機会があったので書きました
組み合わせ
const combination = (array, n) => {
return n === 1
? array.map(x => [x])
: array.flatMap((x,i) => {
return combination(array.slice(i + 1), n - 1)
.map(y => [x].concat(y))
})
}
順列
const permutation = (array, n) => {
return n === 1
? array.map(x => [x])
: array.flatMap((x,i) => {
return permutation(array.slice(0,i).concat(array.slice(i+1)), n-1)
.map(y => [x].concat(y))
})
}
両方
両方を簡単に使えるように、高階関数にしてベース部分を再利用
const itertool = f => (array, n) => {
return n === 1
? array.map(x => [x])
: array.flatMap((x, i) => {
return itertool(f)(f(array, i), n-1)
.map(y => [x].concat(y))
})
}
const comb = (array, i) => array.slice(i+1)
const perm = (array, i) => array.slice(0, i).concat(array.slice(i+1))
const combination = itertool(comb)
const permutation = itertool(perm)
console.log(combination([1, 2, 3], 2))
// expected : [[1, 2], [1, 3], [2, 3]]
console.log(permutation([1, 2, 3], 2)
// expected : [[1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2]]
考え方（分かってる人はスルー推奨）
どうやって書いたの？と聞かれたことがあるので、具体例を出してみます。
ある配列から任意の数の要素取り出す組み合わせを全探索し、返す関数を考える
// 今回は以下の配列から、n個の要素を抜き出す
[1, 2, 3, 4, 5]
// 関数の使い方 （n = 3の時）
console.log(combination([1, 2, 3, 4, 5], 3))
// 期待する出力
[[1,2,3],[1,2,4],[1,2,5],
[1,3,4],[1,3,5],[1,4,5],
[2,3,4],[2,3,5],[2,4,5],
[3,4,5]]
上記の元の配列から任意の数だけ抜き出そうとすると、それぞれ以下のようになる
5C1 （n = 1の時）
5C1 ─ [1], [2], [3], [4], [5]
5C2 （n = 2の時）
5C2 ┬ [1,4C1] - [1,2],[1,3],[1,4],[1,5]
├ [2,3C1] - [2,3],[2,4],[2,5]
├ [3,2C1] - [3,4],[3,5]
└ [4,1C1] - [4,5]
5C3 （n = 3の時）
5C3 ┬ [1,4C2] ┬ [1,2,3C1] - [1,2,3],[1,3,4],[1,4,5]
│ ├ [1,3,2C1] - [1,3,4],[1,3,5]
│ └ [1,4,1C1] - [1,4,5]
├ [2,3C2] ┬ [2,3,2C1] - [2,3,4],[2,3,5]
│ └ [2,4,1C1] - [2,4,5]
└ [3,2C2] ─ [3,4,1C1] - [3,4,5]
なんとなく再帰処理が使えそうな気がするけど、いきなり作るのは大変そうなので、ますは再帰処理を使わず、関数内に n = 1 ~ n = 3 の処理を別々で書くとこんな感じ。
配列の要素の0番目から順に一つの数字を選んでいき、選ばれた数字と過去に選ばれた数字を除いた残りの配列から、さらに数字を選んで配列に格納することになります。
const combination = (array, n) => {
if(n === 1) return array.map(x => [x])
if(n === 2) return array.flatMap((x, i) => {
return array.slice(i+1).map(y => [x, y])
})
if(n === 3) return array.flatMap((x, i) => {
return array.slice(i + 1).flatMap((y, j) => {
return array.slice(i + j + 2).map(z => [x, y, z])
})
})
・・・
// （ n = 4以降も続く）
}
で、これを再帰処理で記述したのが、先に書いた出来上がりのものになります。
参考にしたサイト ・ 参考にすべきサイト
正直、使うだけなら下のサイトにあるコードを持ってくれば、なんの不自由もありません。自分で組めなかった頃は大変参考にさせていただきました。
で、これはこの記事書いてる最中に見つけたんですが、こんな記事もあったんですね。
正直これ理解できる人には、今書いた記事はいらない。笑