JavaScriptで関数型っぽく順列組み合わせを書いてみた

## 気が向いたので追記分(8/27)
- combinationしか書いてませんでしたが、permutationも追記
- 関数のベース部分を共通化し、高階関数として書き直したverも追記
## この記事について
### 背景
なんとなく、JSを関数型っぽく書くのにハマっている時期がありまして。
普段はネットとかで拾ってきたコードを簡単に書き直して使うことが多かったりするのですが、必要に駆られて関数型"っぽく" 順列・組み合わせを全探索するコードを書くことがあったので、備忘的に載せておこうと思います。

### ここで言う順列・組み合わせとは？
高校数学で習う順列とか組み合わせのこと。
パターンの個数を求めるとき、下の式で表せる奴らです（n, mは自然数, n >= m）。
 
```math
_nP_m = n (n-1) (n-2)…(n-m+1)
```
```math
_nC_m = \frac{n(n-1)(n-2)…(n-m+1)}{m(m-1)(m-2)…2・1} 
```

### やったこと
配列から任意の個数の要素を抜き出して配列を作るとき、
全てのパターンを要素として持つ配列を返す関数を、「関数型っぽく」作りました。

## 出来上がり
割と簡潔に書けたんじゃないかと思います。
~~タイトル詐欺的ですが、コードは組み合わせしかありません。sliceの部分を少し改造したらいいだけですし、まぁいいかな、と。欲しいって人がいたら書くかも。~~（[Dartでは書いてみた](https://qiita.com/kamekame85/items/daa4f9f96d0136f0803c)）
機会があったので書きました

### 組み合わせ
``` combination.js
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))
		})
}
```

### 順列
``` permutation.js
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))
    })
}
```

### 両方
両方を簡単に使えるように、高階関数にしてベース部分を再利用
``` itertool.js
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]]
```



## 考え方（分かってる人はスルー推奨）
どうやって書いたの？と聞かれたことがあるので、具体例を出してみます。
ある配列から任意の数の要素取り出す組み合わせを全探索し、返す関数を考える

```js
// 今回は以下の配列から、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番目から順に一つの数字を選んでいき、選ばれた数字と過去に選ばれた数字を除いた残りの配列から、さらに数字を選んで配列に格納することになります。

```js
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以降も続く）
}
```

で、これを再帰処理で記述したのが、先に書いた出来上がりのものになります。


## 参考にしたサイト ・ 参考にすべきサイト

　正直、使うだけなら下のサイトにあるコードを持ってくれば、なんの不自由もありません。自分で組めなかった頃は大変参考にさせていただきました。

- [You Look Too Cool](https://stabucky.com/wp/archives/5334)
- [JavaScriptで順列と組み合わせ](https://qiita.com/s-katsumasa/items/7b8ce83df22467f74c51)
- [ジェネレータで順列と組み合わせを逐次的に生成する](https://webtechdays.com/?p=801)

　で、これはこの記事書いてる最中に見つけたんですが、こんな記事もあったんですね。
正直これ理解できる人には、今書いた記事はいらない。笑

- [JavaScript: 順列 / 組み合わせ / 重複順列 / 重複組み合わせ を まとめて関数にしてみた。](https://qiita.com/ttatsf/items/a98719ad9e1f72ddecca)