разумно генерируя комбинации комбинаций - PullRequest
Новая
       16

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

4 голосов
/ 26 октября 2009

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

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

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

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

Ответы [ 4 ]

5 голосов
/ 26 октября 2009

Ну, есть (30 C 5 * 25 C 5 * 20 C 5 * 15 C 5 * 10 С 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]

Таким образом, вы создаете каждый раздел только один раз

1 голос
/ 06 мая 2011

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

Одной из возможностей было бы найти все комбинации для формирования отдельной группы, а затем пройти и создать комбинации, которые не содержат членов этой отдельной группы. Что-то вроде: 

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

0 голосов
/ 26 октября 2009

Вы можете выполнить некоторую постобработку перестановок. Некоторый псевдокод (реализованный на языке по вашему выбору ...): 

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

Наверное, не самый эффективный; Я бы добавил сортировку и сравнение к коду, который генерирует перестановки лично.

...