ミックステープメーカー

math.combinatoricsボキャブラリーは、要素の集まりについて2種類の疑問に答えてくれます。

• 組み合わせ：順序を無視してグループを選ぶとき、何通りの選び方があるか、あるいはどのように選ぶか？
• 順列：順序が意味を持つとき、要素を並べる方法は何通りあるか、あるいはどのように並べるか？

それぞれの疑問には、数値を返す数え上げのワードと、実際の選択結果を返す列挙のワードがあります。

数え上げ

nCk（n choose k）は、n個の要素からk個の要素からなる組み合わせを何通り選べるかを返します。

nCk ( n k -- m )

USING: math.combinatorics prettyprint ;

5 2 nCk .    ! => 10
6 3 nCk .    ! => 20
5 5 nCk .    ! => 1

nPkは、n個の要素から順序を付けて選んだk個の要素（順列）が何通り作れるかを返します。順序が意味を持つ分、その個数は対応するnCk以上になります。

nPk ( n k -- m )

5 2 nPk .    ! => 20
6 3 nPk .    ! => 120

組み合わせの列挙

all-combinationsは、シーケンスのk個の要素からなるすべての部分集合を返します。各組み合わせの中では要素の元の順序が保たれ、組み合わせは辞書順で返されます。

all-combinations ( seq k -- combinations )

{ 1 2 3 } 2 all-combinations .
! => { { 1 2 } { 1 3 } { 2 3 } }

すべてを集めるのではなく、生成される各組み合わせをその都度処理したいだけなら、ストリーミング形式のeach-combinationを使います。これは組み合わせごとにクオーテーションを呼び出します。

each-combination ( seq k quot -- )

{ 1 2 3 } 2 [ . ] each-combination
! => { 1 2 }
! => { 1 3 }
! => { 2 3 }

順列の列挙

all-permutationsは、シーケンスのすべての並べ方を返します。

all-permutations ( seq -- permutations )

{ 1 2 } all-permutations .
! => { { 1 2 } { 2 1 } }

{ 1 2 3 } all-permutations .
! => { { 1 2 3 } { 1 3 2 } { 2 1 3 } { 2 3 1 } { 3 1 2 } { 3 2 1 } }

そのストリーミング版がeach-permutationで、並べ方ごとにクオーテーションを呼び出します。

each-permutation ( seq quot -- )

{ 1 2 } [ . ] each-permutation
! => { 1 2 }
! => { 2 1 }