JavaScript:配列の順列と組み合わせ

# 追記
共通部分があるのでくくりだしてみました。

```js:
// 共通
const innerPC = filter => pres => xs => k => 
  (k==0)? [pres]
  : xs.flatMap(
      (e, i)=>
        [ ...innerPC(filter)( [...pres, e] )( filter(xs)(i) )( k-1 ) ]
    )

// 順列
const permFilter = xs => i =>
  xs.filter( (_, j)=> j!==i )
const perm =  innerPC( permFilter )( [] )

// 組み合わせ
const combiFilter = xs => i =>
  xs.filter( (_, j)=> j>i )
const combi = innerPC( combiFilter )( [] )

//ジェネレータ版
// 共通部分
const innerPCG = filter => pres => xs => k => function*(){
  if(k===0) yield pres
  for(const i of xs.keys()) yield* innerPCG(filter)( [...pres, xs[i]] )( filter(xs)(i) )( k-1 )
}()

// 順列
const permFilter = xs => i =>
  xs.filter( (_, j)=> j!==i )
const permG =  innerPCG( permFilter )( [] )

// 組み合わせ
const combiFilter = xs => i =>
  xs.filter( (_, j)=> j>i )
const combiG = innerPCG( combiFilter )( [] )
```
# 以下、過去記事

[JavaScriptによる順列組み合わせの生成](https://qiita.com/higuma/items/5af4e62bdf4df42ce673)
[JavaScriptで順列と組み合わせ](https://qiita.com/s-katsumasa/items/7b8ce83df22467f74c51)の@hogefugaのコメントのワンライナーを見て勉強になったので、配列からk個の順列、組み合わせを取り出せる関数を考えてみた。

```js:
//順列
const innerP = pres => xs => k => 
  (k===0)? [pres]
  : xs.flatMap(
      (e, i)=>
        [ ...innerP( [...pres, e] )( xs.filter((_, j)=> j!==i) )( k-1 ) ]
    )

const perm =  innerP([])

//組み合わせ
const innerC = pres => xs => k =>
  (k===0)? [pres]
  : xs.flatMap(
      (e, i)=>
        [ ...innerC( [...pres, e] )( xs.filter( (_, j)=>j>i) )( k-1 ) ]
    )

const combi = innerC([])

//使用例：
perm([0,1,2])(2)
//=> [ [ 0, 1 ], [ 0, 2 ], [ 1, 0 ], [ 1, 2 ], [ 2, 0 ], [ 2, 1 ] ]
combi([0,1,2])(2)
//=> [ [ 0, 1 ], [ 0, 2 ], [ 1, 2 ] ]
```
アルゴリズムは参照記事と(多分)同じ。

+ kが0なら `[pres]` を返す
+ 未確定要素の配列xsの要素一つを確定要素の配列presの最後尾に加える( `[...pres,e]` )
+ 条件でxsの要素を選別する( `xs.filter(条件)` )。
    - 順列の場合、presの最後尾に加えたものと違う( `j!==i` )、
    - 組み合わせの場合、presの最後尾に加えたものより添字が大きい( `j>i` )
+ 、以下をxsの全要素について行い、配列にする
    + 引数 `[...pres,e]`、`xs.filter(条件)`、`k-1` で再帰的に関数を適用しスプレッド構文で配列にする

という感じなのですが、mapを使うと配列の階層が深くなっていってしまうので、flatMapを使っています。
[Array.prototype.flatMap()](https://developer.mozilla.org/ja/docs/Web/JavaScript/Reference/Global_Objects/Array/flatMap)実験的な機能なので実装されていないブラウザがあります。reduceとconcatまたはreduceとスプレッド構文で代替できます。

```js:
//reduceとスプレッド構文を使って:
//innerPの場合：
const innerP = pres => xs => k =>
  (k===0)? [pres]
  : xs.reduce(
      (acc, e, i)=>
        [ ...acc, ...innerP( [...pres, e] )( xs.filter((_, j)=> j!==i) )( k-1 ) ]
      , []
    )

//innerCの場合：
const innerC = pres => xs => k =>
  (k===0)? [pres]
  : xs.reduce(
      (acc, e, i)=>
        [ ...acc, ...innerC( [...pres, e] )( xs.filter((_, j)=> j>i) )( k-1 ) ]
      , []
    )
```
# 追記： ジェネレーターにする
ほとんど同じですが、ジェネレーターにしてみました。

```js:
//順列
const innerPG = pres => xs => k => function*(){
  if(k===0) yield pres
  for(const i of xs.keys() )yield* innerPG([...pres,xs[i]])(xs.filter((_,j)=>j!==i))(k-1)
  return
} ()

const permG = innerPG([])

//組み合わせ
const innerCG = pres => xs => k => function*(){
  if(k===0) yield pres
  for(const i of xs.keys() )yield* innerCG([...pres,xs[i]])(xs.filter((_,j)=>j>i))(k-1)
  return
} ()

const combiG = innerCG([])

//使用例：
> [...permG([0,1,2])(2)]
=> [ [ 0, 1 ], [ 0, 2 ], [ 1, 0 ], [ 1, 2 ], [ 2, 0 ], [ 2, 1 ] ]
> [...combiG([0,1,2])(2)]
=> [ [ 0, 1 ], [ 0, 2 ], [ 1, 2 ] ]
```