믹스테이프 제작자

math.combinatorics 보캐뷸러리는 항목 모음에 관해 두 가지 종류의 질문에 답해요.

• 조합: 순서를 무시하고 그룹을 고르는 방법은 몇 가지이고, 또 어떤 방법들일까요?
• 순열: 순서가 중요한 상황에서 항목을 나열하는 방법은 몇 가지이고, 또 어떤 방법들일까요?

각 질문에는 숫자를 반환하는 개수 세기 단어와 실제로 선택된 항목을 반환하는 나열 단어가 있어요.

개수 세기

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 }