Son muchísimas más combinaciones de 36. De hecho me salen 22680. (Actualización Todo esto es incorrecto. La respuesta definitiva está bajo "Actualización 2". Dejo no obstante la respuesta original para que se vea el proceso de cómo se ha ido llegando a la respuesta buena)
Me ha costado bastante dar con un algoritmo que las genere todas, y he tenido que recurrir a la recursividad. Aún así el algoritmo es bastante difícil de entender. Te presento de momento el código sin explicaciones y un ejemplo del resultado de su ejecución para una lista de sólo 5 números, que ya produce 30 casos. Las explicaciones después.
Código
from itertools import combinations
def todas_las_parejas(elementos):
if len(elementos) <=2:
return [[list(elementos)]]
else:
result = []
for pareja in combinations(elementos, 2):
for resto in todas_las_parejas(set(elementos)-set(pareja)):
caso = [list(pareja)]
caso.extend(resto)
result.append(caso)
return result
Ejemplo de ejecución:
resultado = todas_las_parejas([1,2,3,4,5])
print(len(resultado))
for caso in resultado:
print(caso)
30
[[1, 2], [3, 4], [5]]
[[1, 2], [3, 5], [4]]
[[1, 2], [4, 5], [3]]
[[1, 3], [2, 4], [5]]
[[1, 3], [2, 5], [4]]
[[1, 3], [4, 5], [2]]
[[1, 4], [2, 3], [5]]
[[1, 4], [2, 5], [3]]
[[1, 4], [3, 5], [2]]
[[1, 5], [2, 3], [4]]
[[1, 5], [2, 4], [3]]
[[1, 5], [3, 4], [2]]
[[2, 3], [1, 4], [5]]
[[2, 3], [1, 5], [4]]
[[2, 3], [4, 5], [1]]
[[2, 4], [1, 3], [5]]
[[2, 4], [1, 5], [3]]
[[2, 4], [3, 5], [1]]
[[2, 5], [1, 3], [4]]
[[2, 5], [1, 4], [3]]
[[2, 5], [3, 4], [1]]
[[3, 4], [1, 2], [5]]
[[3, 4], [1, 5], [2]]
[[3, 4], [2, 5], [1]]
[[3, 5], [1, 2], [4]]
[[3, 5], [1, 4], [2]]
[[3, 5], [2, 4], [1]]
[[4, 5], [1, 2], [3]]
[[4, 5], [1, 3], [2]]
[[4, 5], [2, 3], [1]]
Discusión del resultado
Como ves, los 30 casos que aparecen no son los 10 que esperarías si aplicaras la fórmula de "combinaciones de 5 elementos tomados de 2 en 2". Y es que las combinaciones de 5 elementos de 2 en 2 sí que son efectivamente 10, estas 10:
(1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5)
pero esas 10 no son toda la historia. Son sólo las 10 posibles formas que tiene de comenzar cada uno de los (30) casos del resultado. Una vez hemos elegido una de esas combinaciones, por ejemplo (1,2), aún queda el resto de la lista (3,4,5) de la que podemos tomar de nuevo combinaciones de 2 en 2 (otros 3 casos: (3,4), (3,5) y (4,5)). En este ejemplo en que la lista tiene 5 elementos ahí termina la cosa ya que una vez elegido uno de esos segundos casos ya sólo queda un posible elemento para elegir.
De ahí salen por tanto los 30 casos. Tenemos 10 posibles formas de empezar y para cada una de ella otras 3 posibles formas de seguir.
En el caso de tener 9 números la fórmula básicamente se convierte en:
C(9,2) * C(7,2) * C(5,2) * C(3,2)
Siendo C(n,m) el número de combinaciones de n elementos tomados de m en m. Si haces los números sale:
36*21*10*3 = 22680
que son los que produce efectivamente el código que puse más arriba.
Explicación del código
El código usa recursividad, que básicamente se traduce en:
- Resolver el problema para un caso trivial: cuando la lista tiene sólo dos números o menos.
- Resolver el problema para otra lista cualquiera, suponiendo que ya tenemos una función que lo hace por nosotros para una lista más pequeña.
El código hace lo siguiente:
En el caso de que la lista recibida tenga dos elementos o menos, simplemente retorna una lista de listas que tiene dentro la pareja de elementos (o un elemento solo). Por ejemplo, si recibe como parámetro una lista con [2,3], retornaría [[[2,3]]]
. Si recibe como parámetro una lista con el 9, retornaría [[[9]]]
.
Si te fijas, esa respuesta es correcta. Contiene todas las formas de agrupar por parejas la lista que ha recibido como parámetro.
En otro caso debemos construir una lista con todos los casos posibles. Para ello:
- Enumeramos (gracias a
itertools.combinations()
) todas las posibles formas de comenzar nuestro caso (que son todas las combinaciones de la lista dada, tomando sus elementos de dos en dos)
- Para cada una de esas parejas:
- Quitamos de la lista original esa pareja (usando aritmética de conjuntos para hacerlo más simple)
- Llamamos a la función que suponemos ya sabe resolver el problema para una lista más pequeña.
- El resultado de llamar a esa función será una lista con todas las formas de agrupar por parejas los elementos de la sublista. Así que creamos un nuevo caso por cada uno de los casos retornados. Cada nuevo caso comienza con la pareja en cuestión y sigue con cada uno de los casos que nos ha retornado la función "mágica".
- Vamos añadiendo a una lista cada caso generado
- Finalmente retornamos esa lista
Sólo falta por escribir la función "mágica" que sabe resolver el problema para una sublista. Pero, gracias a las maravillas de la recursividad resulta que ya tenemos esa función ¡es la que acabamos de escribir!
Aunque parezca increíble (a mi lo de la recursividad siempre me lo parece), funciona. Basta que la función se llame a sí misma.
Actualización
El código anterior genera casos que sólo se diferencian en el orden de las combinaciones. Por ejemplo, entre las salidas anteriores aparecen:
[[1, 4], [3, 5], [2]]
[[3, 5], [1, 4], [2]]
Actualización 2 Lo que sigue está mal. Contiene un sutil bug que explico y corrijo más adelante, en la Actualización 2
Para evitarlo hay que modificar el código ligeramente. En lugar de hacer que cada pareja sea una lista, haré que sea una tupla. La diferencia en nuestro caso es que las tuplas se pueden meter en conjuntos, y las listas no. Así cada "caso" se puede reducir a un conjunto y en ellos el orden no importa por lo que dos casos que sólo se diferencien en el orden darán lugar al mismo conjunto. Voy agregando esos conjuntos al resultado si no estaban ya antes.
Un problema de los conjuntos es que no tienen orden interno tampoco a la hora de mostrarlos, por lo que los resultados finales podrían mostrar casos como [(1,), (3,4), (2,5)]
, es decir, el elemento "solitario" ya no aparecería necesariamente al final.
Para evitar ese detalle "estético", mantengo dos listas. Una de resultados normal (igual que la de la solución inicial) y otra de conjuntos. Esta segunda la uso sólo para evitar meter casos repetidos en la primera.
Este es el nuevo código:
from itertools import combinations
def todas_las_parejas(elementos):
if len(elementos) <=2:
return [[tuple(elementos)]]
else:
result = []
diferentes = []
for pareja in combinations(elementos, 2):
for resto in todas_las_parejas(set(elementos)-set(pareja)):
caso = [tuple(pareja)]
caso.extend(resto)
if set(caso) not in diferentes:
result.append(caso)
diferentes.append(set(caso))
return result
Y ahora al ejecutar para [1,2,3,4,5]
salen sólo 15 casos:
[(1, 2), (3, 4), (5,)]
[(1, 2), (3, 5), (4,)]
[(1, 2), (4, 5), (3,)]
[(1, 3), (2, 4), (5,)]
[(1, 3), (2, 5), (4,)]
[(1, 3), (4, 5), (2,)]
[(1, 4), (2, 3), (5,)]
[(1, 4), (2, 5), (3,)]
[(1, 4), (3, 5), (2,)]
[(1, 5), (2, 3), (4,)]
[(1, 5), (2, 4), (3,)]
[(1, 5), (3, 4), (2,)]
[(2, 3), (4, 5), (1,)]
[(2, 4), (3, 5), (1,)]
[(2, 5), (3, 4), (1,)]
Para los 9 dígitos la cosa se ha reducido a 2235 casos. Pero no sabría decirte cuál es la fórmula general de donde sale este número (otro reto! maldita sea!)
Actualización 2
El código anterior tiene un bug (ya me extrañaba a mi que el número final de combinaciones para las 9 cifras fuese de 2235, que no factoriza bien pues es 3x5x149, un extraño trío de primos que no pintaba nada bien).
El bug se hace patente si generamos la lista de combinaciones para el caso [4,5,6,7,8]
, en lugar de [1,2,3,4,5]
. Obviamente deberían salir el mismo número de combinaciones (15), pero en cambio salen 27. Examinando los resultados encuentro que aparecen casos "duplicados" que no deberían estar:
[(4, 5), (8, 6), (7,)]
[(6, 8), (4, 5), (7,)]
El problema aquí es que la pareja (8,6)
es considerada diferente de la pareja (6,8)
, por lo que el conjunto de diferentes combinaciones las considera de hecho dos combinaciones diferentes válidas.
El caso no aparecía cuando usamos como entrada [1,2,3,4,5]
porque casualmente para ese caso todas las tuplas generadas iban por orden creciente. Es decir, en cada tupla generada (x,y)
se cumplía que x<y
. Por tanto nunca aparecía la versión (y,x)
de esa misma tupla.
Este comportamiento puede considerarse un accidente. En realidad no tenemos garantías del orden en que van a salir las tuplas, debido a que cuando llamamos recursivamente a la función ya no le estamos pasando una lista, sino un conjunto (set(elementos)-set(pareja)
). itertools.combinations()
iterará sobre los elementos de ese conjunto para generar parejas, pero un conjunto no da garantías sobre el orden en que retornará sus elementos, por lo que podría haber retornado como primera pareja tanto (3,4)
como (4,3)
.
Ese comportamiento accidental de la lista [1,2,3,4,5]
por el cual las tuplas se generaban casualmente ordenadas, aparece también para otras listas. Pero en cambio desaparece en la lista [4,5,6,7,8]
donde empiezan ya a verse tuplas no ordenadas y que por tanto no son reconocidas como repeticiones.
Solución al bug
Para que la tupla (x,y)
sea considerada igual que la tupla (y,x)
lo mejor es dejar ya de usar tuplas para representar las combinaciones, y usar también conjuntos.
Aparentemente por tanto bastaría por cambiar en el código antes visto todas las apariciones de la palabra tuple()
por set()
. Sin embargo no es tan fácil.
Problemas:
- Una tupla puede ser miembro de otro conjunto, pero un
set()
no. No todos los tipos de datos python pueden ser miembros de un conjunto. Sólo los que son hashables (y en particular inmutables). Esta fue en primer lugar la razón por la que había cambiado listas por tuplas, para poder meterlas en conjuntos. Si lo vuelvo a cambiar a set()
ya no puedo meterlo en un conjunto, cosa que necesito para reconocer casos repetidos.
- El problema se arregla si en vez de
set()
uso frozenset()
para representar cada pareja. Este es un tipo especial de conjunto al que no se pueden añadir ni quitar elementos. Es decir, un conjunto inmutable, que por tanto es hashable y puede formar parte de otros conjuntos.
El único problema de frozenset()
es que nos ensucia mucho la salida del programa, porque ahora entonces una posible combinación se mostraría así al imprimirla:
[frozenset({1, 2}), frozenset({3, 4}), frozenset({5})]
en vez de así:
[{1, 2}, {3, 4}, {5}]
Por suerte es fácil definir cómo quieres que se imprima una clase propia. En el siguiente código defino mi clase MySet
, que hereda de frozenset()
, pero redefine el método __repr__()
para que la salida por pantalla sea más compacta y legible. Uso esta clase donde antes usaba tuple()
.
from itertools import combinations
class MySet(frozenset):
def __repr__(self):
return "{%s}" % (", ".join(str(e) for e in self))
def todas_las_parejas_sin(elementos):
if len(elementos) <=2:
return [[MySet(elementos)]]
else:
result = []
diferentes = set()
for pareja in combinations(elementos, 2):
for resto in todas_las_parejas_sin(set(elementos)-set(pareja)):
caso = [MySet(pareja)]
caso.extend(resto)
if MySet(caso) not in diferentes:
result.append(caso)
diferentes.add(MySet(caso))
return result
Ejemplo de ejecución:
for caso in todas_las_parejas_sin([1,2,3,4]):
print(caso)
[{1, 2}, {3, 4}]
[{1, 3}, {2, 4}]
[{1, 4}, {2, 3}]
Ahora funciona correctamente para el caso en que la entrada sea [4,5,6,7,8]
, produciendo 15 combinaciones en lugar de 27.
Y para el caso en que la entrada es [1,2,3,4,5,6,7,8,9]
el número de combinaciones generadas es de sólo 945 (en lugar de 2235).
Bonus
He encontrado la fórmula para el número total de combinaciones que ha de salir. Basta dividir el número calculado originalmente (22680) entre factorial de 4 (24) y sale 945. Esto es porque en cada caso hay 4 parejas, cuyo orden no importa y por tanto dividimos por el número de permutaciones de esos 4 elementos.
La fórmula general sería dividir entre el factorial del número de parejas que se forman para cada caso. Es decir:
def num_casos(n):
resultado = 1
n_parejas = 0
while n>1:
resultado *= C(n, 2) # Combinaciones de n elementos tomados de 2 en 2
n -= 2
n_parejas += 1
return resultado/factorial(n_parejas)
(Faltaría implementar la función C(n,m)
y factorial(n)
)
[1,2] = [2,1]
. permutación:[1,2] != [2,1]