Творець мікстейпу

Бібліотека math.combinatorics відповідає на два види запитань про колекцію елементів:

• Комбінації: скількома способами, або якими саме способами, можна вибрати групу, не враховуючи порядок?
• Перестановки: скількома способами, або якими саме способами, можна упорядкувати елементи, де порядок має значення?

Для кожного запитання є лічильне слово, яке повертає число, і перелічувальне слово, яке повертає самі вибрані набори.

Підрахунок

nCk («n choose k») повертає, скільки k-елементних комбінацій можна вибрати з n елементів:

nCk ( n k -- m )

USING: math.combinatorics prettyprint ;

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

nPk повертає, скільки впорядкованих вибірок із k елементів (перестановок) можна утворити з n елементів. Оскільки порядок має значення, це число принаймні не менше за відповідне 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 }