generare intelligentemente combinazioni di combinazioni

Question

Diciamo che ho una classe di 30 studenti e voglio generare ogni possibile modo in cui possano essere suddivisi in gruppi di 5 (l'ordine è irrilevante).

So come trovare tutte le combinazioni di studenti per formare un gruppo singolarmente ( http: // www .merriampark.com / comb.htm ). Usando quell'iteratore e alcune ricorsioni, posso trovare PERMUTAZIONI delle possibili combinazioni di gruppi. Tuttavia, l'ordine in cui i gruppi sono selezionati non è rilevante e vorrei ridurre al minimo i tempi di esecuzione. Quindi, come posso trovare le COMBINAZIONI uniche dei possibili gruppi?

L'algoritmo di cui sopra utilizza l'ordinamento lessicografico per evitare la generazione di combinazioni duplicate ... c'è un modo in cui posso usare quell'idea sui gruppi anziché sugli oggetti?

Conosco bene Ruby e Java / Python meno bene. Grazie in anticipo per qualsiasi consiglio!

Answer 1

Bene, c'è (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 partizioni diverse di 30 in gruppi di 5, quindi la loro generazione richiederà del tempo, indipendentemente dal metodo utilizzato.

In generale, tuttavia, un buon metodo per selezionare una tale partizione consiste nell'utilizzare un po 'di ordinamento sugli elementi, trovare il raggruppamento per l'elemento non raggruppato più alto e quindi raggruppare il 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]

In questo modo stai generando ogni partizione una sola volta

Answer 2

Questa è una vecchia domanda, ma comunque, per la cronaca, ecco come lo farei 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

Uso un enumeratore perché l'output può crescere molto rapidamente, un output rigoroso (un array per esempio) non sarebbe utile. Un esempio di utilizzo:

>> 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

Potresti fare qualche post-elaborazione sulle permutazioni. Alcuni pseudo-codice (implementare nella lingua di vostra scelta ...):

// 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);
   }
}

Probabilmente non il più efficiente; Aggiungerei l'amplificatore di tipo &; confronta con il codice che genera personalmente le permutazioni.

Answer 4

Una possibilità sarebbe quella di trovare tutte le combinazioni per formare un singolo gruppo, quindi esaminare e generare combinazioni che non contengono membri di quel singolo gruppo. Qualcosa del tipo:

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);
    }
}

Non sarà il metodo più efficace per farlo, ma dovrebbe generare tutte le combinazioni di gruppi. Sospetto che si potrebbero ottenere prestazioni migliori se si generassero elenchi temporanei di combinazioni, in cui in tutti i gruppi che non possono verificarsi sono stati rimossi, ma sarebbe un po 'più complesso.

A parte ciò, dovrebbero esserci 142.506 combinazioni di 30 studenti per formare un singolo gruppo di 5. Il mio < sarcasm > fantastico < / sarcasm > le abilità matematiche suggeriscono che dovrebbero esserci circa 10 ^ 17 = 100 quadrilioni di combinazioni di gruppi di studenti (30! / ((5! ^ 6) * 6!); 30! ordinamenti degli studenti, l'ordine di 6 gruppi di 5 non ha importanza e l'ordine di quei 6 gruppi non ha importanza). Potresti essere seduto lì un po 'in attesa che finisca.