一种有效的方法来组合成组而不重复？
An efficient approach to combinations of pairs in groups without repetitions?
在我开始之前，我需要承认我不是数学家，如果可能的话，我需要用外行的术语来解释。感谢您对此的耐心等待。
问题：一个 class 由 n 个学生组成，我想在整个学年中将他们配对。
对数为n/2。我想尽可能多地让学生与新人一起工作，因此穷尽所有可能的组合。排列无关紧要——学生 1 + 学生 2 与学生 2 + 学生 1 相同。
构建所有非重复对组合的有效方法是什么？
一种方法（由 Aleksei Malushkin 建议）是找到所有唯一对，然后通过暴力破解所有无效组来找到 n/2 对组的所有组合。
在 Ruby 中查找所有唯一对很简单：[1,2,3,4,5,6,7,8].combination(2).to_a 提供了所有 2 项对的数组。
然而，我需要的是制作所有由 4 对组成的小组，每个小组没有重复的学生。如果 class 由 20 名学生组成，我将需要每组 10 对。
蛮力方法会创建对的所有组合并丢弃包含重复对的组合，但是随着学生人数的增加，这种方法很快就会崩溃。
这是解决 8 名学生的 ruby 代码：
# 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
当运行时，这个returns:
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 多名参与者的 class，因此这种方法显然行不通。
问题 1：构造这些组合的有效方法是什么？
查看结果，在我看来有效组的数量是 n/2 - 1，因为学生只能属于 n/2 个可能的对之一。
我的感觉是 仅构建有效的 groups_without_repetition 比创建所有可能的组并丢弃无效的组更有效。我不确定如何处理这个过程，非常感谢您的帮助。
问题 2：如何解决奇数学生的问题？
这可能需要单独讨论，所以我不会担心，除非它有已知的解决方案。
一个。在其中一名学生必须参加两次以容纳奇数的情况下
b。在其中一对变成三重奏的情况下
在每一种情况下，属于上述非常规配对的学生都应排除在更多例外之外，以便尽可能多地轮换。
有生成此类对的有效方法 - round-robin tournament
将所有学生排成两排。
a b c
d e f
因此对是 a-d, b-e, c-f
固定第一个，循环旋转其他的
a d b
e f c
a e d
f c b
a f e
c b d
a c f
b d e
因此生成 N-1 个游览，每个游览具有 N/2 个非重复对。
对于奇数允许唯一的学生休息:)
或者将他（顶行右边的一个）添加到左边的一对中，以获得他遇到两个伙伴之间的最长时间
a b c d
e f g
a-e-d, b-f, c-g
在我开始之前，我需要承认我不是数学家，如果可能的话，我需要用外行的术语来解释。感谢您对此的耐心等待。
问题：一个 class 由 n 个学生组成，我想在整个学年中将他们配对。
对数为n/2。我想尽可能多地让学生与新人一起工作，因此穷尽所有可能的组合。排列无关紧要——学生 1 + 学生 2 与学生 2 + 学生 1 相同。
构建所有非重复对组合的有效方法是什么？
一种方法（由 Aleksei Malushkin 建议）是找到所有唯一对，然后通过暴力破解所有无效组来找到 n/2 对组的所有组合。
在 Ruby 中查找所有唯一对很简单：[1,2,3,4,5,6,7,8].combination(2).to_a 提供了所有 2 项对的数组。
然而，我需要的是制作所有由 4 对组成的小组，每个小组没有重复的学生。如果 class 由 20 名学生组成，我将需要每组 10 对。
蛮力方法会创建对的所有组合并丢弃包含重复对的组合，但是随着学生人数的增加，这种方法很快就会崩溃。
这是解决 8 名学生的 ruby 代码：
# 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
当运行时，这个returns:
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 多名参与者的 class，因此这种方法显然行不通。
问题 1：构造这些组合的有效方法是什么？
查看结果，在我看来有效组的数量是 n/2 - 1，因为学生只能属于 n/2 个可能的对之一。
我的感觉是 仅构建有效的 groups_without_repetition 比创建所有可能的组并丢弃无效的组更有效。我不确定如何处理这个过程，非常感谢您的帮助。
问题 2：如何解决奇数学生的问题？
这可能需要单独讨论，所以我不会担心，除非它有已知的解决方案。
一个。在其中一名学生必须参加两次以容纳奇数的情况下
b。在其中一对变成三重奏的情况下
在每一种情况下，属于上述非常规配对的学生都应排除在更多例外之外，以便尽可能多地轮换。
有生成此类对的有效方法 - round-robin tournament
将所有学生排成两排。
a b c
d e f
因此对是 a-d, b-e, c-f
固定第一个，循环旋转其他的
a d b
e f c
a e d
f c b
a f e
c b d
a c f
b d e
因此生成 N-1 个游览，每个游览具有 N/2 个非重复对。
对于奇数允许唯一的学生休息:)
或者将他（顶行右边的一个）添加到左边的一对中，以获得他遇到两个伙伴之间的最长时间
a b c d
e f g
a-e-d, b-f, c-g