разумно генерируя комбинации комбинаций

Question

Допустим, у меня есть класс из 30 студентов, и я хочу генерировать все возможные способы, которыми они могут быть разбиты на группы по 5 человек (порядок не имеет значения).

Я знаю, как найти все комбинации учеников, чтобы сформировать одну группу индивидуально ( http: // www .merriampark.com / comb.htm ). Используя этот итератор и некоторую рекурсию, я могу найти РАЗЪЕМЫ возможных комбинаций групп. Однако порядок, в котором выбираются группы, не имеет значения, и я хотел бы минимизировать время выполнения. Итак, как мне найти уникальные КОМБИНАЦИИ возможных групп?

Приведенный выше алгоритм использует лексикографическое упорядочение, чтобы избежать создания дублирующих комбинаций ... есть ли способ, которым я могу использовать эту идею в группах, а не в объектах?

Я хорошо знаю Ruby и менее хорошо знаю Java / Python. Заранее спасибо за любой совет!

Answer 1

Ну, есть (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 различных разбиений по 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

Это старый вопрос, но в любом случае, для протокола, как бы я это делал в 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]]]

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

Это не самый эффективный метод, но он должен генерировать все комбинации групп. Я подозреваю, что лучшая производительность могла бы быть, если бы вы генерировали временные списки комбинаций, где во всех группах, которые не могут появляться, были удалены, но это было бы немного сложнее.

В некотором смысле, необходимо составить 142 506 комбинаций из 30 студентов, чтобы сформировать одну группу из пяти человек. My < sarcasm > удивительный < / sarcasm > математические навыки предполагают, что должно быть около 10 ^ 17 = 100 квадриллионов комбинаций групп студентов (30! / ((5! ^ 6) * 6!); 30! заказов студентов, порядок 6 групп из 5 не имеет значения и порядок этих 6 групп не имеет значения). Вы можете сидеть там и ждать, пока это закончится.