¿Qué es un algoritmo de partición de la $nk$ objetos de un total de $\frac{1}{n}\binom{nk}{k}$ de veces, cada vez la fabricación de subconjuntos de tamaño exactamente $k$, de modo que ningún subconjunto de tamaño $k$ es repetido jamás?
Por ejemplo, si $n=k=3$, luego tenemos a $9$ objetos y queremos que la partición en grupos de tamaño $3$. Debemos golpear todos los $\binom{9}{3}=84$ combinaciones en $\frac{1}{3}\binom{9}{3}=28$ particiones. Para este ejemplo, el enfoque ingenuo de la iteración a través de todas las permutaciones de orden y con avidez la elección de los primeros que trabajar (como se muestra a continuación) no es suficiente; se puede alcanzar sólo a $72$ de la $84$ combinaciones.
$[(0, 1, 2), (3, 4, 5), (6, 7, 8)], [(0, 1, 3), (2, 4, 6), (5, 7, 8)], [(0, 1, 4), (2, 3, 7), (5, 6, 8)], [(0, 1, 5), (2, 3, 6), (4, 7, 8)], [(0, 1, 6), (2, 3, 8), (4, 5, 7)], [(0, 1, 7), (2, 3, 5), (4, 6, 8)], [(0, 1, 8), (2, 3, 4), (5, 6, 7)], [(0, 2, 3), (1, 5, 8), (4, 6, 7)], [(0, 2, 4), (1, 5, 6), (3, 7, 8)], [(0, 2, 5), (1, 4, 7), (3, 6, 8)], [(0, 2, 6), (1, 3, 7), (4, 5, 8)], [(0, 2, 7), (1, 3, 8), (4, 5, 6)], [(0, 2, 8), (1, 4, 5), (3, 6, 7)], [(0, 3, 4), (1, 5, 7), (2, 6, 8)], [(0, 3, 5), (1, 4, 6), (2, 7, 8)], [(0, 3, 6), (1, 4, 8), (2, 5, 7)], [(0, 3, 7), (1, 6, 8), (2, 4, 5)], [(0, 4, 6), (1, 2, 7), (3, 5, 8)], [(0, 4, 7), (1, 2, 8), (3, 5, 6)], [(0, 4, 8), (1, 2, 6), (3, 5, 7)], [(0, 5, 7), (1, 3, 6), (2, 4, 8)], [(0, 5, 8), (1, 3, 4), (2, 6, 7)], [(0, 6, 7), (1, 2, 5), (3, 4, 8)], [(0, 6, 8), (1, 3, 5), (2, 4, 7)]$
Básicamente, esto es equivalente a manera Eficiente partición de un conjunto a todos los exclusivos posibles combinaciones de pares, pero en lugar de la división en parejas, yo soy la división en subgrupos de tamaño $k$.
