組み合わせのインテリジェントな生成

StackOverflow https://stackoverflow.com/questions/1622574

  •  06-07-2019
  •  | 
  •  

質問

30人の生徒のクラスがあり、5人のグループに分割できるあらゆる方法を生成したいとします（順序は関係ありません）。

学生のすべての組み合わせを見つけて1つのグループを個別に形成する方法を知っています（ http：// www .merriampark.com / comb.htm ）。その反復子といくつかの再帰を使用することで、可能なグループの組み合わせのPERMUTATIONSを見つけることができます。ただし、グループが選択される順序は関係ないため、実行時間を最小限に抑えたいと思います。では、可能なグループの一意の組み合わせを見つけるにはどうすればよいですか？

上記のアルゴリズムは辞書編集の順序を使用して重複した組み合わせを生成しないようにします...オブジェクトではなくグループでそのアイデアを使用できる方法はありますか？

RubyとJava / Pythonの知識はあまりありません。アドバイスをありがとうございます！

役に立ちましたか？

解決

まあ、（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 30の異なるパーティトンを5つのグループに分けるため、どのメソッドを使用しても、すべての生成には時間がかかります。

ただし、一般的に、このようなパーティションを選択する良い方法は、要素に何らかの順序を使用し、グループ化されていない最も高い要素のグループ化を見つけて、残りをグループ化することです。

     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]

この方法では、各パーティションを一度だけ生成します

他のヒント

これは古い質問ですが、記録のために、とにかく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

出力は非常に速く成長する可能性があるため、列挙子を使用します。厳密な出力（配列など）は役に立たないでしょう。使用例：

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

順列に対していくつかの後処理を行うことができます。疑似コード（選択した言語で実装...）：

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

おそらく最も効率的ではありません。ソート<！> amp;を追加します。順列を個人的に生成するコードと比較してください。

1つの可能性は、すべての組み合わせを見つけて個々のグループを形成し、そのグループのメンバーを含まない組み合わせを実行して生成することです。次のようなもの：

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

これを実行するのに最も効率的な方法ではありませんが、グループのすべての組み合わせを生成する必要があります。一時的な組み合わせのリストを生成すると、パフォーマンスが向上する可能性があると考えられます。発生しないグループはすべて削除されますが、それはもう少し複雑になります。

ちょっとした余談ですが、30人の学生の142,506の組み合わせで5つの単一グループを形成する必要があります。私の<！> lt; sarcasm <！> gt;素晴らしい<！> lt; / sarcasm <！> gt;数学のスキルは、学生グループの約10 ^ 17 = 100兆個の組み合わせがあることを示唆しています（30！/（（5！^ 6）* 6！）; 30！学生の順序、5グループの6グループの順序は関係ありません、これらの6つのグループの順序は関係ありません）。これが完了するのを待っている間、あなたはしばらくそこに座っているかもしれません。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top