Generando inteligentemente combinaciones de combinaciones

Question

Digamos que tengo una clase de 30 estudiantes y quiero generar todas las formas posibles en que se pueden dividir en grupos de 5 (el orden es irrelevante).

Sé cómo encontrar todas las combinaciones de estudiantes para formar un grupo individualmente ( http: // www .merriampark.com / comb.htm ). Al usar ese iterador y algo de recursión, puedo encontrar PERMUTACIONES de las posibles combinaciones de grupo. Sin embargo, el orden en que se seleccionan los grupos no es relevante y me gustaría minimizar mi tiempo de ejecución. Entonces, ¿cómo encuentro las COMBINACIONES únicas de los posibles grupos?

El algoritmo anterior usa el orden lexicográfico para evitar generar combinaciones duplicadas ... ¿hay alguna manera de que pueda usar esa idea en grupos en lugar de en objetos?

Conozco bien a Ruby y Java / Python. Gracias de antemano por cualquier consejo!

Answer 1

Bueno, hay (30 _C 5 * 25 _C 5 * 20 _C 5 * 15 _C 5 * 10 _C 5 * 5 _C 5) / 6! = 30! / (6! * 5! ⁶ ) = 123,378,675,083,039,376 particiones diferentes de 30 en grupos de 5, por lo que generarlos a todos llevará algún tiempo, sin importar el método que uses.

Sin embargo, en general, un buen método para seleccionar una partición de este tipo es utilizar un orden en los elementos y encontrar la agrupación para el elemento desagrupado más alto, y luego agrupar el resto.

     find_partition = lambda do |elts|
        if elts.empty?
         [[]]
        else
         highest = elts.pop
         elts.combination(4).map do |others|
            find_partition[elts - others].map { |part| part << [highest,*others] }
         end.inject(:+)
        end
     end
     find_partition[(1..30).to_a]

De esta forma solo generará cada partición una vez

Answer 2

Esta es una vieja pregunta, pero de todos modos, para el registro, así es como lo haría en Ruby:

class Array
  def groups_of_size(n)
    Enumerator.new do |yielder|
      if self.empty?
        yielder.yield([])
      else
        self.drop(1).combination(n-1).map { |vs| [self.first] + vs }.each do |values|
          (self - values).groups_of_size(n).each do |group|
            yielder.yield([values] + group)
          end   
        end
      end
    end
  end
end

Uso un enumerador porque la salida puede crecer muy rápidamente, una salida estricta (una matriz, por ejemplo) no sería útil. Un ejemplo de uso:

>> pp [0, 1, 2, 3, 4, 5].groups_of_size(3).to_a
=> 
[[[0, 1, 2], [3, 4, 5]],
 [[0, 1, 3], [2, 4, 5]],
 [[0, 1, 4], [2, 3, 5]],
 [[0, 1, 5], [2, 3, 4]],
 [[0, 2, 3], [1, 4, 5]],
 [[0, 2, 4], [1, 3, 5]],
 [[0, 2, 5], [1, 3, 4]],
 [[0, 3, 4], [1, 2, 5]],
 [[0, 3, 5], [1, 2, 4]],
 [[0, 4, 5], [1, 2, 3]]]

Answer 3

Podría realizar un procesamiento posterior en las permutaciones. Algunos pseudocódigos (implementar en el idioma que elija ...):

// We have a list of lists called 'permutations'
// combinations is an (empty) list of lists
for each permutation in permutations
{
   sortedPermutation = permutation.sort()
   if (! combinations.find(sortedPermutation) )
   {
       combinations.add(sortedPermutation);
   }
}

Probablemente no sea el más eficiente; Añadiría el tipo & Amp; comparar con el código que genera las permutaciones personalmente.

Answer 4

Una posibilidad sería encontrar todas las combinaciones para formar un grupo individual, luego revisar y generar combinaciones que no contengan miembros de ese grupo individual. Algo así como:

List<List<Student>> combinations=Combinations(students);
public void GenerateCombinations(int startingIndex, List<List<Student>> currentGroups, int groupsLeft)
{
    if(groupsLeft==0) ProcessCombination(currentGroups);

    for(int i=startingIndex; i<combinations.Count; i++)
    {
        if combinations[i] does not contain a student in current groups
            GenerateCombinations(i+1, currentGroups + combinations[i], groupsLeft -1);
    }
}

No será el método más eficiente para hacerlo, pero debería generar todas las combinaciones de grupos. Sospecho que se podría obtener un mejor rendimiento si generara listas temporales de combinaciones, donde en todos los grupos que no pueden ocurrir se eliminaron, pero eso sería un poco más complejo.

Como un pequeño aparte, debe haber 142,506 combinaciones de 30 estudiantes para formar un solo grupo de 5. Mi < sarcasmo > impresionante < / sarcasm > las habilidades matemáticas sugieren que debería haber aproximadamente 10 ^ 17 = 100 billones de combinaciones de grupos de estudiantes (30! / ((5! ^ 6) * 6!); 30! órdenes de estudiantes, ordenar 6 grupos de 5 no importa , y el orden de esos 6 grupos no importa). Es posible que estés sentado allí esperando que esto termine.