El vocabulario math.combinatorics responde a dos
tipos de preguntas sobre una colección de elementos:
-
Combinaciones: ¿de cuántas maneras, o de qué maneras, puedes elegir un
grupo, sin importar el orden?
-
Permutaciones: ¿de cuántas maneras, o de qué maneras, puedes ordenar
elementos, cuando el orden importa?
Para cada pregunta hay una palabra de conteo que devuelve un número y
una palabra de listado que devuelve las selecciones reales.
Conteo
nCk («n choose 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 de n elementos. Como el orden importa, el conteo es al
menos tan grande como el nCk correspondiente:
nPk ( n k -- m )
5 2 nPk . ! => 20
6 3 nPk . ! => 120
Listado de combinaciones
all-combinations devuelve cada subconjunto 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 recopilarlas 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 }
Listado de permutaciones
all-permutations devuelve cada ordenación 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 contraparte de flujo es each-permutation, que llama a una
quotation con cada ordenación:
each-permutation ( seq quot -- )
{ 1 2 } [ . ] each-permutation
! => { 1 2 }
! => { 2 1 }
Ejercicio de aprendizaje
