Criador de Mixtapes

O vocabulário math.combinatorics responde a dois tipos de perguntas sobre uma coleção de itens:

• Combinações: de quantas formas, ou de que formas, podes escolher um grupo, ignorando a ordem?
• Permutações: de quantas formas, ou de que formas, podes dispor os itens, quando a ordem importa?

Para cada pergunta há uma palavra para contar, que devolve um número, e uma palavra para listar, que devolve as seleções propriamente ditas.

Contagem

nCk («n escolhe k») devolve quantas combinações de k elementos se podem escolher a partir de n itens:

nCk ( n k -- m )

USING: math.combinatorics prettyprint ;

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

nPk devolve quantas seleções ordenadas de k elementos (permutações) se podem fazer a partir de n itens. Como a ordem importa, a contagem é no mínimo tão grande como a do nCk correspondente:

nPk ( n k -- m )

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

Listar combinações

all-combinations devolve todos os subconjuntos de k elementos de uma sequência. Os elementos dentro de cada combinação mantêm a ordem original e as combinações são devolvidas por ordem lexicográfica:

all-combinations ( seq k -- combinations )

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

Quando só queres processar cada combinação à medida que é produzida, em vez de as recolher todas, usa a forma em streaming each-combination, que chama uma quotation com cada combinação:

each-combination ( seq k quot -- )

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

Listar permutações

all-permutations devolve todas as ordenações de uma sequência:

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 } }

A sua equivalente em streaming é each-permutation, que chama uma quotation com cada ordenação:

each-permutation ( seq quot -- )

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