文档建议反馈控制台
首页
学习
活动
专区
圈层
工具
MCP广场
文章/答案/技术大牛
发布
社区首页 >问答首页 >教师算法

问教师算法
EN

Stack Overflow用户
提问于 2013-04-25 06:27:26
回答 1查看 253关注 0票数 4

问题所在

我妈妈是个老师。她最近要求我写一个脚本，其中包含学生的列表，并生成一组学生对。每个学生都应该与其他学生配对，并且没有一个学生与同一个学生一起工作超过一次。

例如，假设她有四个学生："Bob"，"Lisa"，"Duke"和"Tyrone"。脚本应该产生以下输出：

代码语言：javascript
复制
{ { "Bob", "Lisa" }, { "Duke", "Tyrone" } }
{ { "Bob", "Duke" }, { "Lisa", "Tyrone" } }
{ { "Bob", "Tyrone" }, { "Lisa", "Duke" } }

天真尝试

我原以为这是一个简单的项目，但我意识到，在编写代码的过程中，编写一个高效的算法来生成列表有点超出了我的能力。最初，我用Ruby编写了这个天真的实现：

代码语言：javascript
复制
# 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)!中，显然这个解决方案是行不通的。

更好的方法

我很早就意识到我不需要翻阅每一双可能的对子。由于每个学生与其他每个学生一起工作一次，联合结果集应该导致每一个独特的可能的配对。我决定从生成这套集开始。首先，我看了每一个可能的组合。

代码语言：javascript
复制
     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

然后，我把学生们一起工作的那两对拔掉了。

代码语言：javascript
复制
     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

最后，我删除了重复的对。

代码语言：javascript
复制
     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中，生成这些对非常简单。

代码语言：javascript
复制
# 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)

接下来，我试图找出如何将这些独特的对转化为我正在寻找的结果集。我的想法是为每个列表创建一组所有可能的对，然后删除不能用作每个列表中的对的对。在我的第一次尝试中，我尝试在开始下一个列表之前填写每个列表：

代码语言：javascript
复制
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中失败，因为没有可能使用的对。接下来，我尝试在另一个方向运行该算法：

代码语言：javascript
复制
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步之后，很明显算法将失败。

下一步是什么？

很明显我漏掉了一些数学原理。怎么做才是对的？谢谢你提前提供帮助！

algorithm
math
combinatorics
discrete-mathematics
EN

回答 1

Stack Overflow用户

回答已采纳

发布于 2013-04-25 07:33:30

遍历所有对的经典算法如下所示：

  1. 让每个人成对排列(在这里，这对是1-5，2-6，等等)： 1 2 3 4 5 6 7 8
  2. 为了达到下一个配对，让person 1站着，其他人向右旋转一个位置： 1 3 4 8 2 5 6 7

重复第二步，直到你用完了新的配对或他们的需要，无论什么先来。

这一切的美妙之处在于它太简单了，你可以在一堂课上做的很好。当然也不能用纸牌或其他代币。

票数 13
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：

https://stackoverflow.com/questions/16207837

复制
相关文章

相似问题

领券

腾讯云开发者

扫码关注腾讯云开发者

扫码关注腾讯云开发者

领取腾讯云代金券

热门产品

热门推荐

更多推荐

Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有 

深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 粤公网安备44030502008569号

腾讯云计算（北京）有限责任公司 京ICP证150476号 |  京ICP备11018762号

问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档