Прежде чем я начну, я должен признать, что я не математик и, если возможно, нуждался бы в этом объяснении в терминах мирян.Я ценю ваше терпение с этим.
Проблема: класс, состоящий из n учеников, с которыми я хотел бы объединиться в течение учебного года.
Количество пар равно n / 2.Я бы хотел, чтобы студенты работали с новыми людьми как можно больше, и исчерпали все возможные комбинации.Перестановки не имеют значения - ученик 1 + ученик 2 такой же, как ученик 2 + ученик 1.
Как эффективно построить все неповторяющиеся комбинации пар?
В одну сторону, (предложено Алексеем Малушкиным), состоит в том, чтобы найти все уникальные пары, а затем все комбинации n / 2 парных групп путем грубого вытеснения всех недопустимых групп.
Найти все уникальные пары тривиально в Ruby:[1,2,3,4,5,6,7,8].combination(2).to_a предоставляет массив всех пар из 2 элементов.
Однако мне нужно создать все группы, состоящие из 4 пар в каждой, в каждой группе без повторения учащихся.Если класс состоит из 20 учеников, мне понадобятся все группы по 10 пар.
Подход брутфорс создает все комбинации пар и отбрасывает те, которые содержат повторяющиеся пары, но это быстро распадается с большим количествомстудентов.
Вот код рубина, который решает для 8 студентов:
# Ruby 2.5.3
students = [1,2,3,4,5,6,7,8]
possible_pairs = students.combination(2).to_a # https://ruby-doc.org/core-2.4.1/Array.html#method-i-combination
puts "Possible pairs: (#{possible_pairs.size}) #{possible_pairs}"
puts "Possible pair combinations: #{possible_pairs.combination(a.size/2).size}"
groups_without_repetition = possible_pairs.
combination(students.size/2). # create all possible groups with students.size/2 (4) members each
each_with_object([]) do |group, accumulator| # with each of these groups, and an "accumulator" variable starting as an empty array
next unless group.flatten.uniq.length == (students.size) # skip any group with repeating elements
next if accumulator.find {|existing_group| existing_group & group != []} # skip any group that may be found in the accumulator
accumulator << group # add any non-skipped group to the accumulator
end # returnn the value of the accumulator and assign it to groups_without_repetition
puts "actual pair combinations without repetition (#{groups_without_repetition.size}):"
groups_without_repetition.each_with_index do |arr, i|
puts "#{i+1}: #{arr}"
end
При запуске это возвращает:
Possible pairs: (28) [[1, 2], [1, 3], [1, 4], [1, 5], [1, 6], [1, 7], [1, 8], [2, 3], [2, 4], [2, 5], [2, 6], [2, 7], [2, 8], [3, 4], [3, 5], [3, 6], [3, 7], [3, 8], [4, 5], [4, 6], [4, 7], [4, 8], [5, 6], [5, 7], [5, 8], [6, 7], [6, 8], [7, 8]]
Possible pair combinations: 376740
actual pair combinations without repetition (7):
1: [[1, 2], [3, 4], [5, 6], [7, 8]]
2: [[1, 3], [2, 4], [5, 7], [6, 8]]
3: [[1, 4], [2, 3], [5, 8], [6, 7]]
4: [[1, 5], [2, 6], [3, 7], [4, 8]]
5: [[1, 6], [2, 5], [3, 8], [4, 7]]
6: [[1, 7], [2, 8], [3, 5], [4, 6]]
7: [[1, 8], [2, 7], [3, 6], [4, 5]]
Это, однако, не эффективно.При наличии только 12 студентов возможные пары составляют 66, а возможные комбинации пар - 90858768. Я рассчитываю применить это в классе с более чем 80 участниками, поэтому такой подход явно не сработает.
Вопрос 1:Каким был бы эффективный подход для построения этих комбинаций?
Глядя на результаты, мне кажется, что число допустимых групп равно n / 2 - 1, поскольку учащийся может принадлежать только одному из n /2 возможные пары.
Я чувствую, что было бы эффективнее создать только действительные groups_without_repetition вместо создания всех возможных групп и выбрасывания недействительных.Я не уверен, как подойти к этому процессу, и был бы признателен за вашу помощь.
Вопрос 2: Как подойти к этому с нечетным количеством студентов?
Возможно, это отдельное обсуждение.поэтому я не стал бы беспокоиться об этом, если у него нет известного решения.
a.В случае, если одному из студентов придется участвовать дважды, чтобы разместить нечетное число
b.В случае, когда одна из пар станет трио
В каждом из этих случаев учащиеся, которые были частью вышеупомянутых нетрадиционных пар, должны быть исключены из дальнейших исключений для максимально возможного числа вращений..