Generando inteligentemente combinaciones de combinaciones
-
06-07-2019 - |
Pregunta
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!
Solución
Bueno, hay (30 C 5 * 25 C 5 * 20 C 5 * 15 C 5 * 10 C 5 * 5 C 5) / 6! = 30! / (6! * 5! 6 ) = 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
Otros consejos
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]]]
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.
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.