توليد بذكاء مجموعات من تركيبات

Question

ودعونا نقول لدي فئة من 30 طالبا وتريد توليد كل وسيلة ممكنة الذي يمكن تقسيم إلى مجموعات من 5 (أمر غير ذي صلة).

وأنا أعرف كيف للعثور على جميع مجموعات من الطلاب لتشكيل مجموعة واحدة على حدة ( HTTP: // شبكة الاتصالات العالمية .merriampark.com / comb.htm ). باستخدام هذا مكرر وبعض العودية، يمكن أن أجد التباديل تركيبات مجموعة ممكنة. ومع ذلك، الترتيب الذي يتم اختيار المجموعات غير ذي صلة وأود أن تقليل وقت التنفيذ بلدي. فكيف يمكنني العثور على COMBINATIONS فريدة من المجموعات المحتملة؟

والخوارزمية أعلاه يستخدم ترتيب المعجمي لتجنب توليد مجموعات مكررة ... هل هناك طريقة أستطيع أن استخدام هذه الفكرة على مجموعات بدلا من الأشياء؟

وأنا أعلم جيدا روبي وجافا / بيثون أقل أيضا. شكرا مقدما على أي نصيحة!

Answer 1

حسنا، هناك (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 partitons مختلفة من 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]

وبهذه الطريقة كنت توليد إلا مرة واحدة كل قسم

Answer 2

وهذا هو السؤال القديم، ولكن على أي حال، للسجل، وكيف لي ان يفعل ذلك في روبي:

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

وI استخدام العداد لأن الإخراج يمكن أن تنمو بسرعة كبيرة، فإن الناتج صارم (مجموعة على سبيل المثال) لن يكون مفيدا. وهناك مثال الاستعمال:

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

هل يمكن أن تفعل بعض مرحلة ما بعد المعالجة على التباديل. بعض الزائفة مدونة (تنفيذ في اللغة من اختيارك ...):

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

وربما لا يكون الأكثر كفاءة. فما استقاموا لكم فاستقيموا إضافة نوع ومقارنة التعليمات البرمجية التي يولد التباديل شخصيا.

Answer 4

وأحد الاحتمالات سيكون للعثور على كافة تركيبات لتشكيل مجموعة الفردية، ثم انتقل من خلال وتوليد المجموعات التي لا تحتوي على أعضاء تلك المجموعة الفردية. شيء من هذا القبيل:

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

ولن يكون الأسلوب الأكثر فعالية للذهاب نحو ذلك، ولكن يجب أن تولد كل مجموعات من المجموعات. وأظن أفضل أداء يمكن زيارتها لو كنت لتوليد قوائم مؤقتة من المجموعات، حيث أزيلت في جميع المجموعات التي لا يمكن أن يحدث، ولكن ذلك سيكون قليلا أكثر تعقيدا.

وكما طفيف جانبا، ينبغي أن يكون هناك 142506 مجموعات من 30 طالبا لتشكيل مجموعة واحدة من 5. بلدي <سخرية> رهيبة مهارات الرياضيات تشير إلى أن يجب أن تكون هناك حوالي 10 ^ 17 = 100 كوادريليون مجموعات من المجموعات من الطلاب (30 / ((5 ^ 6) * 6)؛!! 30 أوامر شراء من الطلاب، وطلب من 6 مجموعات من 5 لا يهم، وترتيب تلك الجماعات 6 لا يهم). هل يمكن أن يجلس هناك في انتظار لهذا وحتى النهاية.