11

Tengo una lista [1,2,3,4,5,6,7,8,9] y quisiera conseguir todas las listas que surgen a raíz de agrupar sus elementos en parejas y uno solitario, sin importar el orden de las parejas. Es decir, espero algo como:

[[1,2],[3,4],[5,6],[7,8],[9]],
[[1,2],[3,4],[5,6],[7,9],[8]],
[[1,2],[3,4],[5,6],[8,9],[7]],
[[1,2],[3,4],[5,7],[6,8],[9]],
[[1,2],[3,4],[5,7],[6,9],[8]],
...

Como bien indica @abulafia, el número total de listas en el caso de 9 elementos sería:

C(9,2) * C(7,2) * C(5,2) * C(3,2)

donde C(n,m) son las combinaciones de n elementos tomados de m en m. Con 22680 posibilidades como resultado, bastante alejado de las 36 que indicaba.

Un saludo y gracias de antemano

3
  • 1
    [1,2] y [2,1] son equivalentes? Commented el 12 oct. 2018 a las 18:00
  • 1
    tener en cuenta que en matemáticas la diferencia entre combinación y permutación es sutil pero importante al contar el número de casos posibles. combinación: [1,2] = [2,1] . permutación: [1,2] != [2,1] Commented el 12 oct. 2018 a las 20:10
  • 1
    @aloMalbarez Disculpas por no responder hasta ahora. Efectivamente, lo que buscaba eran las combinaciones y no las permutaciones, caso en el que [1,2] == [2,1]
    – Bugzilla
    Commented el 12 oct. 2018 a las 20:18

2 respuestas 2

14

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:

  1. Resolver el problema para un caso trivial: cuando la lista tiene sólo dos números o menos.
  2. 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:

  1. 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.

  2. 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))

15
  • Muchísimas gracias, funciona justo como quería. La dedicación puesta en la respuesta es envidiable y un ejemplo que intentaré seguir. Otra vez, gracias (-:
    – Bugzilla
    Commented el 12 oct. 2018 a las 20:15
  • Me temo que la respuesta, aunque es lo que necesitaba, falla cuando hay elementos pares (4 y 6 probé). Por ejemplo, con 4 elementos: [[1, 2], [3, 4]] y [[3, 4], [1, 2]] aparecen como combinaciones distintas. Para mi problema la solución es válida, unicamente te lo comento por si quieres romperte un poco más la cabeza, aunque repito, no es necesario.
    – Bugzilla
    Commented el 12 oct. 2018 a las 21:12
  • @Bugzilla Ya veo... lo que no veo es por qué está relacionado con que el número de elementos sea par. Supongo que podrá pasar también con impares...
    – abulafia
    Commented el 12 oct. 2018 a las 21:16
  • Efectivamente, con 5 elementos también repite combinaciones: [[3, 4], [1, 2], [5]] y [[1, 2], [3, 4], [5]]. Pero como el caso era generar las combinaciones, con un comparador de listas me desharé de las repetidas.
    – Bugzilla
    Commented el 12 oct. 2018 a las 21:20
  • 1
    @Bugzilla Buenas noticias! Tengo una solución mejor. Lo he puesto en otra respuesta porque extender la anterior ya me parecía demasiado rizar el rizo :-) Siéntete libre de "des-aceptar" la anterior y aceptar la nueva, si crees que resuelve tu problema (que a estas alturas ya no estoy seguro de cuál será la especificación exacta) :-D
    – abulafia
    Commented el 14 oct. 2018 a las 15:12
6

Añado otra respuesta porque extender otra vez la anterior me parece que, además de hacerla demasiado larga, la haría más confusa.

Admitir elementos repetidos en la entrada

En un comentario a la respuesta anterior el usuario (@Bugzilla) menciona la posibilidad de que la lista de entrada pueda tener elementos repetidos. Esto complica bastante la situación ya que, si bien se admiten elementos repetidos en la entrada, no deben admitirse combinaciones repetidas en la salida, pero la semántica exacta de qué puede significar ésto no está del todo clara.

Por ejemplo, asumamos que la lista de entrada es [1,1,2,3] Esos dos 1 que aparecen en la entrada deben considerarse iguales? O son dos 1 "diferentes" en cierto sentido. Si son diferentes, por ejemplo distingámoslos con un subíndice, la secuencia de entrada sería [1₁, 1₂, 2, 3] y las posibles combinaciones serían:

[{1₁, 1₂}, {2, 3}]
[{1₁, 2}, {1₂, 3}]
[{1₁, 3}, {1₂, 2}]

Pero ya que en realidad los dos unos se representan igual, es decir, 1, la salida sería:

[{1, 1}, {2, 3}]
[{1, 2}, {1, 3}]
[{1, 3}, {1, 2}]

en la que aparentemente las dos últimas combinaciones son la misma.

Si la salida anterior fuese válida (aparecen combinaciones "aparentemente" repetidas pero que "en realidad" no lo son porque algunos de sus elementos son "en realidad" diferentes aunque tengan la misma representación), podría lograrse mantienendo en una lista los datos y usando para obtener las parejas otra lista con los índices de esos datos. Una vez obtenidas las parejas de índices, se usan éstos para acceder a los "verdaderos" datos en la primera lista.

Sin embargo si la salida anterior no fuera admisible por considerarse indénticos los dos últimos casos, y por tanto las únicas combinaciones válidas fuesen:

[{1, 1}, {2, 3}]
[{1, 2}, {1, 3}]

entonces aún puede hacerse, pero con otro enfoque.

Otro enfoque

El enfoque consiste en no usar conjuntos para guardar cada pareja, sino regresar a la solución que usaba tuplas, y no usar tampoco conjuntos para descender recursivamente a "combinar" el resto de la lista. En particular, me refiero a la línea:

  for resto in todas_las_parejas(set(elementos)-set(pareja)):

La idea de esa línea es que, una vez hemos extraido una pareja de la lista original, llamamos recursivamente a la función para que nos dé todas las recombinaciones de lo que queda de la lista. Ya que la pareja considerada no tiene por qué corresponder a los dos primeros elementos de la lista elementos, no podemos hacer algo como elementos[2:] para obtener "el resto". Por eso recurrí a aritmética de conjuntos, convirtiendo la lista original en un conjunto y restándole el subconjunto con la pareja extraída.

Naturalmente ese enfoque funcionaba correctamente sólo si no había elementos repetidos en la lista. De otro modo, las conversiones a conjunto harán desaparecer los elementos repetidos.

Pero podemos aún construir la sublista sin más que hacer una copia de la original y a la copia quitarle (con .remove()) los elementos que están en la pareja considerada. El código es un poco más largo, pero no tan complejo como yo me temía.

Aún podemos seguir usando conjuntos para detectar casos repetidos, ya que los elementos de ese conjunto no son ya los números de la lista original, sino las tuplas que hemos sido sacando.

Por otro lado, ya que no hacemos conversiones a conjuntos de la lista de entrada, tenemos garantizado el orden en que se recorrerán los elementos, de modo que si en un momento aparece la tupla (x,y) sabemos que no saldrá ya nunca la tupla (y,x), por lo que ese problema (que nos obligó a usar conjuntos en vez de tuplas) también desaparece.

Solución

En resumen, creo que esta implementación hace por fin lo que se espera, incluso en el caso de que haya elementos repetidos en la lista de entrada:

def todas_las_parejas(elementos):
  if len(elementos) <=2:
    return [[tuple(elementos)]]
  else:
    result = []
    diferentes = []
    for pareja in combinations(elementos, 2):
      sub_lista = elementos[:]
      sub_lista.remove(pareja[0])
      sub_lista.remove(pareja[1])
      for resto in todas_las_parejas(sub_lista):
        caso = [tuple(pareja)]
        caso.extend(resto)
        if set(caso) not in diferentes:
          result.append(caso)
          diferentes.append(set(caso))
    return result

Ejemplos de ejecución:

>>> todas_las_parejas([1,2,3,4])
[[(1, 2), (3, 4)], 
 [(1, 3), (2, 4)], 
 [(1, 4), (2, 3)]]

>>> todas_las_parejas([1,1,2,3])
[[(1, 1), (2, 3)], 
 [(1, 2), (1, 3)]]

>>> todas_las_parejas([1,1,2,3,4])
[[(1, 1), (2, 3), (4,)],
 [(1, 1), (2, 4), (3,)],
 [(1, 1), (3, 4), (2,)],
 [(1, 2), (1, 3), (4,)],
 [(1, 2), (1, 4), (3,)],
 [(1, 2), (3, 4), (1,)],
 [(1, 3), (1, 4), (2,)],
 [(1, 3), (2, 4), (1,)],
 [(1, 4), (2, 3), (1,)]]

>>> todas_las_parejas([1,1,1,2,3])
[[(1, 1), (1, 2), (3,)],
 [(1, 1), (1, 3), (2,)],
 [(1, 1), (2, 3), (1,)],
 [(1, 2), (1, 3), (1,)]]

>>> todas_las_parejas([1,1,1,1,1])
[[(1, 1), (1, 1), (1,)]]
1
  • Sí, está solución es la más robusta. Tras estar probando para varios casos, parece que finalmente no surgen errores inesperados. Muchas gracias por tu ayuda, realmente te gustan los retos y ayudar desinteresadamente (-:
    – Bugzilla
    Commented el 15 oct. 2018 a las 22:31

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.