intelligente Kombinationen von Kombinationen zu erzeugen
-
06-07-2019 - |
Frage
Lassen Sie uns sagen, dass ich eine Klasse von 30 Schülern haben und jede erdenkliche Art und Weise erzeugt werden soll, in denen sie in Gruppen von 5 aufgeteilt werden (Reihenfolge spielt keine Rolle).
Ich weiß, wie alle Kombinationen von Studenten zu finden, individuell eine Gruppe zu bilden ( http: // www .merriampark.com / comb.htm ). Durch die Verwendung dieses Iterator und einig Rekursion, kann ich Permutationen der möglichen Gruppenkombinationen finden. Allerdings Reihenfolge, in der die Gruppen ausgewählt werden, ist nicht relevant, und ich möchte meine Ausführungszeit minimieren. So wie ich die einzigartige Kombination der möglichen Gruppen finden?
Der obige Algorithmus verwendet lexikographische Ordnung doppelte Kombinationen zu vermeiden Erzeugung ... Gibt es eine Möglichkeit, dass ich diese Idee auf Gruppen verwenden kann, anstatt auf Objekte?
Ich weiß, Rubin gut und Java / Python weniger gut. Vielen Dank im Voraus für jede Beratung!
Lösung
Nun, es gibt (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 unterschiedliche partitons von 30 in Gruppen von 5, so zu erzeugen, sie alle werden einige Zeit dauern, egal, welche Methode Sie verwenden.
In der Regel aber eine gute Methode, eine solche Partition um die Auswahl ist etwas Ordnung auf den Elementen zu verwenden, und die Gruppierung für die höchste ungruppierten Element zu finden, und dann die Gruppe der Rest.
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]
Auf diese Weise Sie nur jede Partition einmal zu erzeugen
Andere Tipps
Dies ist eine alte Frage, aber wie auch immer, für die Aufzeichnung, das ist, wie ich würde es in 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
ich einen Enumerator verwenden, weil der Ausgang sehr schnell wachsen kann, ein strikter Ausgang (ein Array zum Beispiel) wäre nicht sinnvoll sein. Ein Anwendungsbeispiel:
>> 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]]]
Sie könnten einige Nachbearbeitung auf den Permutationen tun. Einige Pseudo-Code (implementieren in der Sprache Ihrer Wahl ...):
// 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);
}
}
Wahrscheinlich nicht die effizienteste; Ich würde die Art hinzuzufügen und zu dem Code zu vergleichen, die persönlich die Permutationen erzeugt.
Eine Möglichkeit wäre, alle Kombinationen zu finden, eine einzelne Gruppe zu bilden, dann gehen Sie durch und generieren Kombinationen, die nicht Mitglieder dieser einzelnen Gruppe enthalten. So etwas wie:
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);
}
}
Es wird die effizienteste Methode zu gehen, um es nicht, aber es sollte alle Kombinationen von Gruppen erzeugen. Ich vermute, eine bessere Leistung zu haben war, wenn Sie temporäre Listen von Kombinationen zu erzeugen sind, wo in allen Gruppen, die nicht entfernt wurden auftreten können, aber das wäre ein wenig komplexer sein.
Wie ein leichter beiseite, sollte es 142.506 Kombinationen von 30 Studenten sein, eine einzelne Gruppe von 5. Mein