5

Tengo los números del 1 al 12 que quiero agrupar en cuatro grupos, por ejemplo 1;2;3 - 4;5;6 - 7;8;9 - 10;11;12. Pues bien, quisiera saber como calcular todas las combinaciones posibles

ACLARACIONES:

  • los grupos 1;2;3 y 3;1;2 serían semejantes porque contienen los mismos números, así que solo necesito uno de ellos
  • las soluciones 1;2;3 - 4;5;6 - 7;8;9 - 10;11;12 y 4;5;6 - 1;2;3 - 10;11;12 - 7;8;9 serían semejantes porque contienen los mismos grupos aunque estén en un orden diferente, así que solo necesito uno de ellos.

He escrito a mano todas las combinaciones para los números del 1 al 9 y me salen 280 soluciones

Necesito:

  1. saber si existe alguna fórmula matemática que calcule el número de soluciones
  2. un pseudo-código para poder escribir todas las soluciones con un lenguaje de programación, independientemente de la secuencia de números y la cantidad de grupos.

Pongo un ejemplo concreto y como lo he resuelto, pero no me parece muy "elegante".

Suponiendo una secuencia de números del 1 al 9 (a = 9) y dividiéndolo en grupos de 3 (b = 3), la solución es 280

c = a - b = 6
d = c / b = 2
e = a / b = 3

A = c! / ( (c - b)! * b! * d ) = 6! / ( 3! * 3! * 2 ) = 10
B = ( a! * A ) / ( (a - b)! * b! * e ) = ( 9! * 10 ) / ( 6! * 3! * 3 ) = 280

' despejando:
C = ( (a - 1)! )/( (a - 2b)! * [(b - 1)!]^2 * (a - b) ) = 8! /( 3! * (2!)^2 * 6 ) = 280

La fórmula es:

introducir la descripción de la imagen aquí

De esta forma me sale que para a = 12 hay 1.540 combinaciones o que para a = 30 y b = 6 salen 3.995.986.995 combinaciones

No se muy bien como he llegado a esta ecuación, pero sospecho que seguramente haya alguna ecuación más sencilla y directa y es eso lo que precisamente estoy buscando.


He conseguido crear este código que genera todas las combinaciones que estoy buscando. El problema es que para generarlo tiene que recorrer todas las combinaciones posibles de las tuplas que forman la combinatoria. Para el caso de a=9 y b=3 tiene que combinar las 84 combinaciones y por lo tanto tiene que explorar 95284 combinaciones para poder imprimir las 280 combinaciones válidas, no es ningún problema porque son pocos valores, pero para un caso mayor, por ejemplo a=30 y b=6 es directamente imposible esperar tanto como para conseguir que se imprima siquiera la primera combinación

from itertools import combinations 

a=9
b=3

secuencia = []
for i in range(a):
  secuencia += [i]
comb = list(combinations(secuencia, b))
comb2 = combinations(comb,int(a/b))
mm=0
for i in comb2:
  descartar = False
  for h in range(len(i)):
    resto=[]
    for j in range(len(i)):
      if h > j:
        resto += i[j]
    for k in i[h]:
      if k in resto:
        descartar = True
        break
  if not descartar: 
    mm+=1
    print(i)
print(mm)

NECESITO un código que imprima exactamente el mismo resultado pero sin la necesidad de explorar las combinaciones inválidas (que se descarten directamente los grupos inválidos o con valores repetidos entre sublistas)

2
  • En realidad lo que buscas es una combinacion y no asi una permutacion como indicas, encontraras la formula matematica en google(facil y rapido), y del pseudocodigo, igual buscalo se que habra muchos en internet, tu pregunta asi como esta podria ser cerrada, es mas ya existen votos de cierre, deberias de editarlo.
    – Shassain
    Commented el 5 ene. 2020 a las 14:16
  • No es tan sencillo. Creo que no se está entendiendo (porque no he debido explicarlo bien) lo que me ocurre y en google no he encontrado la respuesta. Sin embargo si que he encontrado una respuesta de manera experimental con excel y voy a editarlo para que se vea reflejado
    – Joracosu
    Commented el 5 ene. 2020 a las 14:43

1 respuesta 1

3

He llegado a una fórmula más sencilla que sería la siguiente:

Fórmula general

Siendo a el número de elementos a agrupar, b el número de elementos en cada grupo, y k el cociente entre a y b (que se supone entero), igual por tanto al número de grupos en cada combinación. Observa que en la fórmula b! está elevado a k

Por ejemplo, para a=9, b=3 se tendría k=3 y la fórmula saldría:

Ejemplo

que es 280, coincidiendo con lo que esperabas. En cambio para los otros casos que ponías no me sale lo mismo. Para a=12, b=3 (se tendría k=4) se obtiene con mi fórmula 15400, mientras que tú decías que eran 1540 (curiosamente diez veces menor). Para a=30, b=6 (por tanto k=5) me salen 11.423.951.396.577.720 combinaciones, muy por encima de las 3.995.986.995 que tú decías (concretamente, me sale un factor 2858856 veces mayor)

Mi demostración

Mi idea parte de que agrupando a elementos de b en b, se pueden formar k=b/a grupos (suponiendo siempre que b es múltiplo de a)

  • El primer grupo estará formado por cualquier combinación de b elementos a tomar entre todos los que hay. El número de tales combinaciones es C(a,b) (número combinatorio a sobre b, o coeficiente binomial)
  • El segundo grupo estará formado otra vez por cualquier combinación de b elementos, pero esta vez no tenemos para elegir todos los a iniciales, pues ya se han usado b elementos en el primer grupo. Por tanto serían b elementos a elegir de un conjunto de (a-b), y por tanto sería el número binomial C(a-b, b)
  • El tercer grupo, de forma análoga, serían b elementos a elegir entre (a-2b) elementos, y por tanto C(a-2b, b)
  • Etc, en cada grupo se va rebajando el numerador del coeficiente binomial en b, hasta que el último grupo sería formado por b elementos a elegir entre (a-(k-1)b), y por tanto sería C(a-(k-1)b, b)

Escribiendo entonces la fórmula completa, el total de agrupaciones que pueden formarse saldría de multiplicar todos esos números combinatorios antes escritos, es decir:

formula

Aquí podrían aparecer elementos repetidos según tu criterio, pues un grupo como (1,2,3) (4,5,6) (7,8,9) sería equivalente a (4,5,6), (1,2,3), (7,8,9) y otras similares. Pero si te das cuenta estos casos son en realidad permutaciones de los bloques. Ya que tenemos 3 bloques habrá 3! de esas permutaciones. En el caso general serían k!, por lo que basta dividir la fórmula anterior por k! para "eliminar" esos casos que se consideran iguales. Haremos esta división al final.

De momento vamos a intentar simplificar la fórmula. Para ello podemos recordar la definición de número combinatorio:

Numero combinatorio

Si usamos esta definición para expandir la fórmula antes escrita, nos queda:

formula

y ahora viene lo bueno. Si te fijas, en el denominador de la primera fracción aparece (a-b)!, que se simplifica con el numerador de la siguiente, y lo mismo pasa con su denominador (a-2b)! que se simplifica con el numerador de la siguiente, etc. por lo que al final queda:

simplificación

En la última fracción aparece (a-kb)!, pero ya que kb es igual a a, esto es el factorial de cero, que por definición es 1, por lo que la expresión completa se reduce a:

Formula final

Si ahora divides eso por k! para "eliminar" las permutaciones de grupos, ya que las consideras soluciones iguales, se llega a la fórmula inicial como se quería demostrar.

Listarlas todas con python

Estoy seguro de que tiene que haber una implementación más eficiente pero de momento sólo se me ha ocurrido lo siguiente:

  • Generar todas las permutaciones de a elementos, con ayuda de itertools.permutations. Esta función es lazy lo que quiere decir que no genera todas las permutaciones cuando se la llama y retorna una lista con ellas, sino que lo que retorna es un generador en el que, cada vez que iteras, se recupera una nueva permutación. Por tanto es eficiente en memoria (aunque no en tiempo) porque a pesar de que hay muchas permutaciones de las que sólo aprovecharemos unas pocas, las que no aprovechamos no ocupan espacio porque las voy descartando.
  • Para cada permutación, agrupo de b en b los elementos de la permutación. Formo así k grupos de b elementos cada uno.
  • Cada grupo lo ordeno (para que si una vez me sale por ejemplo el grupo [1,2,3] pero en otra iteración me sale el [3,2,1], al final ambos acaben siendo el mismo, pues al ordenarlos sale [1,2,3] en ambos casos
  • Convierto cada grupo en una tupla, y genero otra tupla con todos los grupos. De nuevo ordeno esta tupla de tuplas, para que el caso ((1,2,3), (4,5,6) , (7,8,9)) acabe siendo idéntico a ((4,5,6), (7,8,9), (1,2,3)). Observa que ordeno la secuencia de tuplas, pero no el interior de cada tupla (que ya estaba ordenado de antes).
  • Meto la tupla (de tuplas) resultante en un conjunto.

Ya que el conjunto va descartando duplicados, y debido a que las ordenaciones que hice de las tuplas acaban causando duplicados en las permutaciones equivalentes, al final el conjunto tendrá sólo las que buscas.

El código sería éste (la función grouper() la tomé inspirada de una que aparece en la documentación del módulo itertools).

from itertools import permutations

def grouper(lista, k):
    args = [iter(lista)] * k
    return zip(*args)

a = 9
b = 3
k = a//b

total = set()
for combinacion in permutations(range(a)):
  aux = [tuple(sorted(grupo)) for grupo in grouper(combinacion, b)]
  total.add(tuple(sorted(aux)))
print(len(total))

Y salen 280. Pero repito que no me parece muy eficiente tener que generar 9! (362.880) permutaciones para quedarse sólo con 280. Seguiré pensando...

Nota adicional

Tu fórmula y la mía no son equivalentes, aunque ambas dan el mismo resultado para a=9; b=3 (probablemente porque tú sabías que tenía que salir 280 en este caso y "apañaste" una fórmula que diera ese resultado). Curiosamente tu fórmula da también los mismos valores que la mía para otros números pequeños, como a=6, b=3 o a=8, b=4. No obstante en cuanto aumentas a por encima de 9 las fórmulas comienzan a dar valores diferentes.

Por ejemplo, para a=10, b=2, tu fórmula predice 63 combinaciones, pero el script python anterior genera 945, que son los predichos por mi fórmula. Con números mayores ya es difícil de verificar experimentalmente porque el script python se eterniza (es lo que tiene el factorial, crece más rápido aún que la exponencial).

4
  • 1
    No hace falta que pienses más, esta demostración ya nos dejó con la boca abierta a muchos.
    – user166844
    Commented el 24 jun. 2020 a las 18:23
  • si, ya me di cuenta en su día de las discrepancias de las que me hablas entre lo que esperaba y lo que realmente era, aunque tienes que tener en cuenta que al principio lo hice "a mano" y me salté sin querer algunas de las opciones... pero olvidé actualizarlo aquí. Quería resolver un problema de clase con la ayuda de esta pregunta pero me llega un poco tarde la respuesta :D de todas formas MUCHAS GRACIAS, como dice @gabrielcoronel, es impresionante. Se ve que esto se te da bien. Ojalá yo hubiera tenido esto hace 5 meses! me hubieran puesto un 10 en lugar de solo un pobre 9,75 XDDDDDD ¡GRACIAS!
    – Joracosu
    Commented el 25 jun. 2020 a las 7:27
  • De nada. Realmente no me di cuenta de que la pregunta tenía ya varios meses de antigüedad. Ayer me salió en el feed de preguntas recientes, quizás porque alguien la editó. Una pena no haber llegado a tiempo, pero felicidades por el 9,75.
    – abulafia
    Commented el 25 jun. 2020 a las 7:59
  • debió salirte porque alguien dio un positivo a la pregunta hace dos dias. Aunque me haya llegado tarde para ese trabajo, seguro que algún dia alguien le da utilidad a la pregunta. Además la respuesta está muy bien argumentada
    – Joracosu
    Commented el 25 jun. 2020 a las 9:23

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.