Creador de mixtapes

El vocabulario math.combinatorics responde a dos tipos de pregunta sobre una colección de elementos:

• Combinaciones: ¿de cuántas maneras, o de qué maneras, puedes elegir un grupo, sin tener en cuenta el orden?
• Permutaciones: ¿de cuántas maneras, o de qué maneras, puedes ordenar los elementos, cuando el orden importa?

Para cada pregunta hay una palabra de recuento que devuelve un número y una palabra de listado que devuelve las selecciones reales.

Recuento

nCk («n elige k») devuelve cuántas combinaciones de k elementos se pueden elegir de n elementos:

nCk ( n k -- m )

USING: math.combinatorics prettyprint ;

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

nPk devuelve cuántas selecciones ordenadas de k elementos (permutaciones) se pueden hacer a partir de n elementos. Como el orden importa, el recuento es al menos tan grande como el nCk correspondiente:

nPk ( n k -- m )

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

Listar combinaciones

all-combinations devuelve todos los subconjuntos de k elementos de una secuencia. Los elementos dentro de cada combinación mantienen su orden original, y las combinaciones se devuelven en orden lexicográfico:

all-combinations ( seq k -- combinations )

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

Cuando solo quieres procesar cada combinación a medida que se produce, en lugar de recogerlas todas, usa la forma de flujo each-combination, que llama a una quotation con cada combinación:

each-combination ( seq k quot -- )

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

Listar permutaciones

all-permutations devuelve todos los ordenamientos de una secuencia:

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

Su equivalente en flujo es each-permutation, que llama a una quotation con cada ordenamiento:

each-permutation ( seq quot -- )

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