algorithm - 老师的算法

标签 algorithm math combinatorics discrete-mathematics

问题

我妈妈是老师。她最近要求我编写一个脚本，该脚本获取学生列表并生成学生对集。每个学生都应与其他所有学生配对，任何学生都不应与同一名学生合作超过一次。

例如，假设她有四个学生:“Bob”、“Lisa”、“Duke” 和 ”蒂龙”。该脚本应产生以下输出:

{ { "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.index 和 permutations.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 步之后，很明显算法将要失败。

下一步是什么？

这里显然缺少一些数学原理。这样做的正确方法是什么？提前感谢您的帮助!

最佳答案

循环遍历所有对的经典算法是这样的:

  1. 让每个人成对排队(在这里，每对是 1-5、2-6 等):

    1 2 3 4

    5 6 7 8

  2. 要进入下一组，让第 1 个人站着不动，其他人向右旋转一个位置:

    1 3 4 8

    2 5 6 7

重复第 2 步，直到用完新的配对或需要它们为止，无论先到什么。

这一切的美妙之处在于它是如此简单，您可以在体育课上正确完成。当然，也可以使用卡片或其他代币。

关于algorithm - 老师的算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/16207837/

上一篇：algorithm - 通过只遍历一次来测试单链表是否是循环的

下一篇：python - 如何在 python 中实现负无穷大？

相关文章：

algorithm - CLRS 的这段话是什么意思？

string - 有没有比 BK 树更有效的模糊字符串搜索方法？

java - Java中对数字的数字求和

html - 给定一些 AABB，找到包含它们的最小总表面积 AABB？

c++ 数字的 m 位排列

algorithm - 基于距离的大小为 2 的组

algorithm - Tarjan 的强连通分量算法——为什么索引在后边？

math - 点相对于图像坐标的旋转

Python Numpy 向量化组合学的嵌套 for 循环

C# - 组合学

©2024 IT工具网  联系我们