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

追記

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

// 共通
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による順列組み合わせの生成
JavaScriptで順列と組み合わせの@hogefugaのコメントのワンライナーを見て勉強になったので、配列からk個の順列、組み合わせを取り出せる関数を考えてみた。

//順列
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()実験的な機能なので実装されていないブラウザがあります。reduceとconcatまたはreduceとスプレッド構文で代替できます。

//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 ) ]
      , []
    )

追記： ジェネレーターにする

ほとんど同じですが、ジェネレーターにしてみました。

//順列
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 ] ]