问题
我妈妈是老师。她最近要求我编写一个脚本，该脚本获取学生列表并生成学生对集。每个学生都应该与其他学生配对，并且没有学生与同一个学生一起工作超过一次。
例如，假设她有四个学生："Bob"、"Lisa"和。该脚本应产生以下输出："Duke""Tyrone"
{ { "Bob", "Lisa" }, { "Duke", "Tyrone" } }
{ { "Bob", "Duke" }, { "Lisa", "Tyrone" } }
{ { "Bob", "Tyrone" }, { "Lisa", "Duke" } }
天真的尝试
我认为这将是一个简单的项目，但我意识到在编写一个有效的算法来生成列表的过程中，我意识到这有点超出我的能力。最初，我用 Ruby 编写了这个简单的实现：
# the list of students
CLASS_LIST = ("A".."H").to_a
# add an extra element to the class list if the class list length is odd
CLASS_LIST << nil if CLASS_LIST.length.odd?
# determine all possible permutations of the class lists
permutations = CLASS_LIST.permutation
# convert all of the permutations into pairs
permutations = permutations.map { |permutation| permutation.each_slice(2).to_a }
puts "PERMUTATIONS LENGTH: " + permutations.length.to_s
# iterate through the permutations and remove all subsequent permutations that contain a matching
# pair
i = 0
while i < permutations.length
# remove any subsequent permutations that contain pairs already in the current permutation
permutations.delete_if do |permutation|
# return true if the current permutation has any elements in common with the other permutation
permutations.index(permutation) > i and permutations[i].any? do |p1|
permutation.any? do |p2|
(p1[0] == p2[0] and p1[1] == p2[1]) or (p1[0] == p2[1] and p1[1] == p2[0])
end
end
end
# increment i
i += 1
end
permutations.each do |permutation|
p permutation
end
这种实现非常低效。当我分析它时，4 名学生用时 0.093 秒，6 名学生用时 0.376 秒，8 名学生用时 35 分 32 秒。另外，排列的总数是无法控制的。4 个学生有 24 个排列，6 个有 720，8 个有 40320。
渐近地，while循环在 O(n!) 中delete_if运行，循环在 O(n!) 中运行，permutations.indexandpermutations.any?循环在 O(n!) 中permutation.any?运行，内部循环在 O(n) 时间内运行，这意味着整个算法运行在 O(n(n!)^3)! 显然，这个解决方案是行不通的。
更好的方法
我很早就意识到我不需要遍历所有可能的配对。由于每个学生只与其他学生一起工作一次，因此合并结果集应该产生每个唯一的可能对。我决定从生成这个集合开始。首先，我查看了所有可能的组合。
A B C D E F
A A,A A,B A,C A,D A,E A,F
B B,A B,B B,C B,D B,E B,F
C C,A C,B C,C C,D C,E C,F
D D,A D,B D,C D,D D,E D,F
E E,A E,B E,C E,D E,E E,F
F F,A F,B F,C F,D F,E F,F
然后我删除了学生们正在与自己一起工作的配对。
A B C D E F
A A,B A,C A,D A,E A,F
B B,A B,C B,D B,E B,F
C C,A C,B C,D C,E C,F
D D,A D,B D,C D,E D,F
E E,A E,B E,C E,D E,F
F F,A F,B F,C F,D F,E
最后，我删除了重复的对。
A B C D E F
A A,B A,C A,D A,E A,F
B B,C B,D B,E B,F
C C,D C,E C,F
D D,E D,F
E E,F
F
在 Ruby 中生成对相当简单。
# generate the set of all possible pairs
UNIQUE_PAIRS = (0..(CLASS_LIST.length - 2)).to_a.map do |row|
((row + 1)..(CLASS_LIST.length - 1)).to_a.map do |column|
[ row, column ]
end
end.flatten(1)
接下来，我试图弄清楚如何将这些独特的配对转化为我正在寻找的结果集。我的想法是为每个列表创建一组所有可能的对，然后消除无法使用的对，因为对被添加到每个列表中。在我的第一次尝试中，我尝试在开始下一个列表之前填写每个列表：
STEP 0:
LIST 1: { }
LIST 2: { }
LIST 3: { }
LIST 4: { }
LIST 5: { }
AVAILABLE 1: { { A, B }, { A, C }, { A, D }, { A, E }, { A, F }, { B, C }, { B, D }, { B, E }, { B, F }, { C, D }, { C, E }, { C, F }, { D, E }, { D, F }, { E, F } }
AVAILABLE 2: { { A, B }, { A, C }, { A, D }, { A, E }, { A, F }, { B, C }, { B, D }, { B, E }, { B, F }, { C, D }, { C, E }, { C, F }, { D, E }, { D, F }, { E, F } }
AVAILABLE 3: { { A, B }, { A, C }, { A, D }, { A, E }, { A, F }, { B, C }, { B, D }, { B, E }, { B, F }, { C, D }, { C, E }, { C, F }, { D, E }, { D, F }, { E, F } }
AVAILABLE 4: { { A, B }, { A, C }, { A, D }, { A, E }, { A, F }, { B, C }, { B, D }, { B, E }, { B, F }, { C, D }, { C, E }, { C, F }, { D, E }, { D, F }, { E, F } }
AVAILABLE 5: { { A, B }, { A, C }, { A, D }, { A, E }, { A, F }, { B, C }, { B, D }, { B, E }, { B, F }, { C, D }, { C, E }, { C, F }, { D, E }, { D, F }, { E, F } }
STEP 1:
LIST 1: { { A, B } }
LIST 2: { }
LIST 3: { }
LIST 4: { }
LIST 5: { }
AVAILABLE 1: { { C, D }, { C, E }, { C, F }, { D, E }, { D, F }, { E, F } }
AVAILABLE 2: { { A, C }, { A, D }, { A, E }, { A, F }, { B, C }, { B, D }, { B, E }, { B, F }, { C, D }, { C, E }, { C, F }, { D, E }, { D, F }, { E, F } }
AVAILABLE 3: { { A, C }, { A, D }, { A, E }, { A, F }, { B, C }, { B, D }, { B, E }, { B, F }, { C, D }, { C, E }, { C, F }, { D, E }, { D, F }, { E, F } }
AVAILABLE 4: { { A, C }, { A, D }, { A, E }, { A, F }, { B, C }, { B, D }, { B, E }, { B, F }, { C, D }, { C, E }, { C, F }, { D, E }, { D, F }, { E, F } }
AVAILABLE 5: { { A, C }, { A, D }, { A, E }, { A, F }, { B, C }, { B, D }, { B, E }, { B, F }, { C, D }, { C, E }, { C, F }, { D, E }, { D, F }, { E, F } }
STEP 2:
LIST 1: { { A, B }, { C, D } }
LIST 2: { }
LIST 3: { }
LIST 4: { }
LIST 5: { }
AVAILABLE 1: { { E, F } }
AVAILABLE 2: { { A, C }, { A, D }, { A, E }, { A, F }, { B, C }, { B, D }, { B, E }, { B, F }, { C, E }, { C, F }, { D, E }, { D, F }, { E, F } }
AVAILABLE 3: { { A, C }, { A, D }, { A, E }, { A, F }, { B, C }, { B, D }, { B, E }, { B, F }, { C, E }, { C, F }, { D, E }, { D, F }, { E, F } }
AVAILABLE 4: { { A, C }, { A, D }, { A, E }, { A, F }, { B, C }, { B, D }, { B, E }, { B, F }, { C, E }, { C, F }, { D, E }, { D, F }, { E, F } }
AVAILABLE 5: { { A, C }, { A, D }, { A, E }, { A, F }, { B, C }, { B, D }, { B, E }, { B, F }, { C, E }, { C, F }, { D, E }, { D, F }, { E, F } }
STEP 3:
LIST 1: { { A, B }, { C, D }, { E, F } }
LIST 2: { }
LIST 3: { }
LIST 4: { }
LIST 5: { }
AVAILABLE 1: { }
AVAILABLE 2: { { A, C }, { A, D }, { A, E }, { A, F }, { B, C }, { B, D }, { B, E }, { B, F }, { C, E }, { C, F }, { D, E }, { D, F } }
AVAILABLE 3: { { A, C }, { A, D }, { A, E }, { A, F }, { B, C }, { B, D }, { B, E }, { B, F }, { C, E }, { C, F }, { D, E }, { D, F } }
AVAILABLE 4: { { A, C }, { A, D }, { A, E }, { A, F }, { B, C }, { B, D }, { B, E }, { B, F }, { C, E }, { C, F }, { D, E }, { D, F } }
AVAILABLE 5: { { A, C }, { A, D }, { A, E }, { A, F }, { B, C }, { B, D }, { B, E }, { B, F }, { C, E }, { C, F }, { D, E }, { D, F } }
STEP 4:
LIST 1: { { A, B }, { C, D }, { E, F } }
LIST 2: { { A, C } }
LIST 3: { }
LIST 4: { }
LIST 5: { }
AVAILABLE 1: { }
AVAILABLE 2: { { B, D }, { B, E }, { B, F }, { D, E }, { D, F } }
AVAILABLE 3: { { A, D }, { A, E }, { A, F }, { B, C }, { B, D }, { B, E }, { B, F }, { C, E }, { C, F }, { D, E }, { D, F } }
AVAILABLE 4: { { A, D }, { A, E }, { A, F }, { B, C }, { B, D }, { B, E }, { B, F }, { C, E }, { C, F }, { D, E }, { D, F } }
AVAILABLE 5: { { A, D }, { A, E }, { A, F }, { B, C }, { B, D }, { B, E }, { B, F }, { C, E }, { C, F }, { D, E }, { D, F } }
STEP 5:
LIST 1: { { A, B }, { C, D }, { E, F } }
LIST 2: { { A, C }, { B, D } }
LIST 3: { }
LIST 4: { }
LIST 5: { }
AVAILABLE 1: { }
AVAILABLE 2: { }
AVAILABLE 3: { { A, D }, { A, E }, { A, F }, { B, C }, { B, E }, { B, F }, { C, E }, { C, F }, { D, E }, { D, F } }
AVAILABLE 4: { { A, D }, { A, E }, { A, F }, { B, C }, { B, E }, { B, F }, { C, E }, { C, F }, { D, E }, { D, F } }
AVAILABLE 5: { { A, D }, { A, E }, { A, F }, { B, C }, { B, E }, { B, F }, { C, E }, { C, F }, { D, E }, { D, F } }
这在第 6 步失败，因为没有可用的配对。接下来我尝试在另一个方向运行算法：
STEP 1:
LIST 1: { { A, B } }
LIST 2: { }
LIST 3: { }
LIST 4: { }
LIST 5: { }
AVAILABLE 1: { { C, D }, { C, E }, { C, F }, { D, E }, { D, F }, { E, F } }
AVAILABLE 2: { { A, C }, { A, D }, { A, E }, { A, F }, { B, C }, { B, D }, { B, E }, { B, F }, { C, D }, { C, E }, { C, F }, { D, E }, { D, F }, { E, F } }
AVAILABLE 3: { { A, C }, { A, D }, { A, E }, { A, F }, { B, C }, { B, D }, { B, E }, { B, F }, { C, D }, { C, E }, { C, F }, { D, E }, { D, F }, { E, F } }
AVAILABLE 4: { { A, C }, { A, D }, { A, E }, { A, F }, { B, C }, { B, D }, { B, E }, { B, F }, { C, D }, { C, E }, { C, F }, { D, E }, { D, F }, { E, F } }
AVAILABLE 5: { { A, C }, { A, D }, { A, E }, { A, F }, { B, C }, { B, D }, { B, E }, { B, F }, { C, D }, { C, E }, { C, F }, { D, E }, { D, F }, { E, F } }
STEP 2:
LIST 1: { { A, B } }
LIST 2: { { A, C } }
LIST 3: { }
LIST 4: { }
LIST 5: { }
AVAILABLE 1: { { C, D }, { C, E }, { C, F }, { D, E }, { D, F }, { E, F } }
AVAILABLE 2: { { B, D }, { B, E }, { B, F }, { D, E }, { D, F }, { E, F } }
AVAILABLE 3: { { A, D }, { A, E }, { A, F }, { B, C }, { B, D }, { B, E }, { B, F }, { C, D }, { C, E }, { C, F }, { D, E }, { D, F }, { E, F } }
AVAILABLE 4: { { A, D }, { A, E }, { A, F }, { B, C }, { B, D }, { B, E }, { B, F }, { C, D }, { C, E }, { C, F }, { D, E }, { D, F }, { E, F } }
AVAILABLE 5: { { A, D }, { A, E }, { A, F }, { B, C }, { B, D }, { B, E }, { B, F }, { C, D }, { C, E }, { C, F }, { D, E }, { D, F }, { E, F } }
STEP 3:
LIST 1: { { A, B } }
LIST 2: { { A, C } }
LIST 3: { { A, D } }
LIST 4: { }
LIST 5: { }
AVAILABLE 1: { { C, D }, { C, E }, { C, F }, { D, E }, { D, F }, { E, F } }
AVAILABLE 2: { { B, D }, { B, E }, { B, F }, { D, E }, { D, F }, { E, F } }
AVAILABLE 3: { { B, C }, { B, E }, { B, F }, { C, E }, { C, F }, { E, F } }
AVAILABLE 4: { { A, E }, { A, F }, { B, C }, { B, D }, { B, E }, { B, F }, { C, D }, { C, E }, { C, F }, { D, E }, { D, F }, { E, F } }
AVAILABLE 5: { { A, E }, { A, F }, { B, C }, { B, D }, { B, E }, { B, F }, { C, D }, { C, E }, { C, F }, { D, E }, { D, F }, { E, F } }
STEP 4:
LIST 1: { { A, B } }
LIST 2: { { A, C } }
LIST 3: { { A, D } }
LIST 4: { { A, E } }
LIST 5: { { A, F } }
AVAILABLE 1: { { C, D }, { C, E }, { C, F }, { D, E }, { D, F }, { E, F } }
AVAILABLE 2: { { B, D }, { B, E }, { B, F }, { D, E }, { D, F }, { E, F } }
AVAILABLE 3: { { B, C }, { B, E }, { B, F }, { C, E }, { C, F }, { E, F } }
AVAILABLE 4: { { B, C }, { B, D }, { B, F }, { C, D }, { C, F }, { D, F } }
AVAILABLE 5: { { B, C }, { B, D }, { B, E }, { C, D }, { C, E }, { D, E } }
STEP 5:
LIST 1: { { A, B } }
LIST 2: { { A, C } }
LIST 3: { { A, D } }
LIST 4: { { A, E } }
LIST 5: { { A, F } }
AVAILABLE 1: { { C, D }, { C, E }, { C, F }, { D, E }, { D, F }, { E, F } }
AVAILABLE 2: { { B, D }, { B, E }, { B, F }, { D, E }, { D, F }, { E, F } }
AVAILABLE 3: { { B, C }, { B, E }, { B, F }, { C, E }, { C, F }, { E, F } }
AVAILABLE 4: { { B, C }, { B, D }, { B, F }, { C, D }, { C, F }, { D, F } }
AVAILABLE 5: { { B, C }, { B, D }, { B, E }, { C, D }, { C, E }, { D, E } }
STEP 6:
LIST 1: { { A, B }, { C, D } }
LIST 2: { { A, C }, { B, D } }
LIST 3: { { A, D } }
LIST 4: { { A, E } }
LIST 5: { { A, F } }
AVAILABLE 1: { { E, F } }
AVAILABLE 2: { { E, F } }
AVAILABLE 3: { { B, C }, { B, E }, { B, F }, { C, E }, { C, F }, { E, F } }
AVAILABLE 4: { { B, C }, { B, D }, { B, F }, { C, F }, { D, F } }
AVAILABLE 5: { { B, C }, { B, D }, { B, E }, { C, E }, { D, E } }
在第 6 步之后，很明显该算法将失败。
下一步是什么？
显然我在这里缺少一些数学原理。这样做的正确方法是什么？我在这里先向您的帮助表示感谢！