那些遇到过的问题

老师的算法

Lan*_*opp 4 algorithm math combinatorics discrete-mathematics

问题

我妈妈是老师.她最近让我写了一个脚本,其中列出了学生名单并生成了一组学生对.每个学生都应该与其他学生配对,没有学生不止一次与同一个学生一起工作.

例如,假设她有四个学生:"Bob","Lisa","Duke"和"Tyrone".该脚本应生成以下输出:

{ { "Bob", "Lisa" }, { "Duke", "Tyrone" } }
{ { "Bob", "Duke" }, { "Lisa", "Tyrone" } }
{ { "Bob", "Tyrone" }, { "Lisa", "Duke" } }
Run Code Online (Sandbox Code Playgroud)

天真的尝试

我认为这将是一个简单的项目,但我意识到编写一个有效的算法来生成列表的中途有点超出我.最初,我在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
Run Code Online (Sandbox Code Playgroud)

这种实施非常低效.当我描述它时,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
Run Code Online (Sandbox Code Playgroud)

然后我删除了学生们自己一起工作的那对.

     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
Run Code Online (Sandbox Code Playgroud)

最后,我删除了重复对.

     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
Run Code Online (Sandbox Code Playgroud)

在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)
Run Code Online (Sandbox Code Playgroud)

接下来,我试图弄清楚如何将这些独特的对转换为我正在寻找的结果集.我的想法是为每个列表创建一组所有可能的对,然后消除不能作为对添加到每个列表中的对.在我的第一次尝试中,我尝试在开始下一个之前填写每个列表:

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 } }
Run Code Online (Sandbox Code Playgroud)

这在步骤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 } }
Run Code Online (Sandbox Code Playgroud)

在第6步之后,很明显算法将会失败.

下一步是什么？

显然我在这里缺少一些数学原理.这样做的正确方法是什么？我在这里先向您的帮助表示感谢!

Chr*_*zig 13

循环遍历所有对的经典算法如下:

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

    1 2 3 4

    5 6 7 8

  2. 要进入下一个配对,请让人1站立不动,其他人在右侧旋转一个位置:

    1 3 4 8

    2 5 6 7

重复步骤2,直到你没有新的配对或需要它们,无论是什么先发生.

它的美妙之处在于它非常简单,你可以在植物课上做到这一点.或者当然还有卡片或其他代币.

归档时间：

查看次数：

240 次

最近记录：

12 年，7 月 前
相关归档
Google如何"你的意思是？" 算法工作？ 426
阶乘时间算法O(n!)的示例 35
大O,总结一系列n个数字的复杂性是多少？ 25
不同编程范式算法的复杂性 13
浮点除法的软件实现,舍入问题 9
在 Javascript 中比较大数字 8
找到达到某个总和的最小迭代次数 7
从一组点中找到最大矩形的有效算法 7
用Pygame画一条抛物线 1
选择条件下的数学运算 0
难疑归档
如何克隆特定的Git分支？ 2804
命令折叠代码的所有部分？ 1576
无法打开与身份验证代理的连接 1473
传输安全性阻止了明文HTTP 1425
PHP中的startsWith()和endsWith()函数 1409
jQuery document.createElement等价？ 1226
为特定提交生成git补丁 1144
PHP和枚举 1114
如何配置Visual Studio代码以始终在新选项卡中打开文件？ 1078
群集和非群集索引实际上意味着什么？ 1041