Combinatoria

Si queremos calcular el conjunto de secuencias de \(r\) elementos tomados a partir de \(n\) elementos iniciales, podemos Arrangements. También podemos usar NrArrangements para conocer cuántas hay.

Arrangements([1,2,3],2);

[ [ 1, 2 ], [ 1, 3 ], [ 2, 1 ], [ 2, 3 ], [ 3, 1 ], [ 3, 2 ] ]

NrArrangements([1..3],2);

6

Arrangements permite repeticiones el el conjunto de elementos del que escogemos las secuencias.

Arrangements([1,2,2,3],2);

[ [ 1, 2 ], [ 1, 3 ], [ 2, 1 ], [ 2, 2 ], [ 2, 3 ], [ 3, 1 ], [ 3, 2 ] ]

Las permutaciones de una lista se pueden construir con Permutations.

PermutationsList([1..3]);

[ [ 1, 2, 3 ], [ 1, 3, 2 ], [ 2, 1, 3 ], [ 2, 3, 1 ], [ 3, 1, 2 ], [ 3, 2, 1 ] ]

Si lo que queremos son \(n\)-uplas, usamos Tuples.

Tuples([1..3],2);

[ [ 1, 1 ], [ 1, 2 ], [ 1, 3 ], [ 2, 1 ], [ 2, 2 ], [ 2, 3 ], [ 3, 1 ], [ 3, 2 ], [ 3, 3 ] ]

Cuando lo que queremos son conjuntos en vez de secuencias, usamos combinaciones.

Combinations([1..3],2);

[ [ 1, 2 ], [ 1, 3 ], [ 2, 3 ] ]

NrCombinations([1..3],2);

3

Binomial(3,2);

3

El comando PartitionsSet se utiliza para calcular el número de particiones de un conjunto dado.

PartitionsSet([1..3]);

[ [ [ 1 ], [ 2 ], [ 3 ] ], [ [ 1 ], [ 2, 3 ] ], [ [ 1, 2 ], [ 3 ] ], [ [ 1, 2, 3 ] ], [ [ 1, 3 ], [ 2 ] ] ]

Si especificamos un segundo argumento, calcula el número de particiones con cardinal exactamente ese argumento.

PartitionsSet([1..5],2);

[ [ [ 1 ], [ 2, 3, 4, 5 ] ], [ [ 1, 2 ], [ 3, 4, 5 ] ], [ [ 1, 2, 3 ], [ 4, 5 ] ], [ [ 1, 2, 3, 4 ], [ 5 ] ], [ [ 1, 2, 3, 5 ], [ 4 ] ], [ [ 1, 2, 4 ], [ 3, 5 ] ], [ [ 1, 2, 4, 5 ], [ 3 ] ], [ [ 1, 2, 5 ], [ 3, 4 ] ], [ [ 1, 3 ], [ 2, 4, 5 ] ], [ [ 1, 3, 4 ], [ 2, 5 ] ], [ [ 1, 3, 4, 5 ], [ 2 ] ], [ [ 1, 3, 5 ], [ 2, 4 ] ], [ [ 1, 4 ], [ 2, 3, 5 ] ], [ [ 1, 4, 5 ], [ 2, 3 ] ], [ [ 1, 5 ], [ 2, 3, 4 ] ] ]

NrPartitionsSet([1..5],2);

15

El comando Partitions devuelve el número de formas posibles de sumar el argumento entero que pasemos.

Partitions(5);

[ [ 1, 1, 1, 1, 1 ], [ 2, 1, 1, 1 ], [ 2, 2, 1 ], [ 3, 1, 1 ], [ 3, 2 ], [ 4, 1 ], [ 5 ] ]

Podemos calcular cuántas de estas tienen una longitud determinada.

Partitions(5,2);

[ [ 3, 2 ], [ 4, 1 ] ]

Si buscamos particiones ordenadas, hacemos lo siguiente

OrderedPartitions(5);

[ [ 1, 1, 1, 1, 1 ], [ 1, 1, 1, 2 ], [ 1, 1, 2, 1 ], [ 1, 1, 3 ], [ 1, 2, 1, 1 ], [ 1, 2, 2 ], [ 1, 3, 1 ], [ 1, 4 ], [ 2, 1, 1, 1 ], [ 2, 1, 2 ], [ 2, 2, 1 ], [ 2, 3 ], [ 3, 1, 1 ], [ 3, 2 ], [ 4, 1 ], [ 5 ] ]

Así las soluciones enteras positivas de \(x+y=5\) vienen dadas por

OrderedPartitions(5,2);

[ [ 1, 4 ], [ 2, 3 ], [ 3, 2 ], [ 4, 1 ] ]

Iteradores

Muchas de estas funciones tienen una versión con iteradores, para no tener que generarlas todas y almacenarlas en memoria.

IteratorOfCombinations, IteratorOfPartitions, IteratorOfTuples.

InstallMethod(ViewString,[IsIterator], 
function(l) 
    return "Iterator"; 
end);

l:=IteratorOfCombinations([1..4],2);
for i in l do
Print(i," suman ",Sum(i),"\n");
od;

[ 1, 2 ] suman 3
[ 1, 3 ] suman 4
[ 2, 3 ] suman 5
[ 1, 4 ] suman 5
[ 2, 4 ] suman 6
[ 3, 4 ] suman 7

Iterator