这是一个创建于 2241 天前的主题，其中的信息可能已经有所发展或是发生改变。
这个问题叫做 Kirkman's Schoolgirl Problem，即某学校有十五名女生，她们经常每天三人一行、共组成五行去散步，问要怎样安排才能使得在一周的时间里，任何两个女生恰好在同一行中散步一次？
找出一种来不难，网上有很多，我在想怎么能罗列出所有的解法来。不知道大家有什么好办法没有？
15 条回复 • 2018-11-09 14:42:46 +08:00
 |
1
Deville 2018-11-09 10:02:14 +08:00
女生长得好看么；
有微信号么； 哪个学校的； 确定都是女生并没有混入女装大佬么？ |
 |
4
coderluan 2018-11-09 10:28:44 +08:00
直接设置 15 个变量，然后暴力枚举所有情况，最后再挨个检查是否符合要求，没要求复杂度的前提下，暴力枚举就是最好的算法。
|
 |
5
mathzhaoliang 2018-11-09 10:32:17 +08:00
@coderluan 伪代码呢？ talk is cheap, show me the code.
|
 |
6
dikT 2018-11-09 10:35:49 +08:00
|
 |
7
Fulcrum 2018-11-09 10:55:40 +08:00 via Android
像一个复杂的指派规划。。。
|
|
8
coderluan 2018-11-09 11:15:57 +08:00  2
@mathzhaoliang
"talk is cheap, show me the code." 这话是用来解决技术争论的，你没提自己的观点和反对意见，也就是没争论。 现在的情况，是别人帮忙提供解决问题的思路，你却指责对方不给代码，这是什么行为，我不就不说了。 希望你只是不小心滥用了词语。 |
 |
9
ryd994 2018-11-09 11:52:32 +08:00 via iPhone
第一列 A 不动，第二列 B 每次 shift1，第三列 C 每次 shift2
5 天后，所有的 A 都和所有的 B 并排过，所有的 B 都和所有的 C 并排过。这个应该不难证。 剩下 AC 并排关系。A1 和 B135 并排然后绕回来 24 正好 完成 |
|
10
ryd994 2018-11-09 11:54:57 +08:00 via iPhone
等等，还漏了 ABC 各自内部，我再想想
|
 |
11
kenv07 2018-11-09 11:59:23 +08:00
楼上说暴力枚举的，15 的阶乘等于 1,307,674,368,000，所以其实可行就是要花点时间
|
 |
12
wdv2ly 2018-11-09 11:59:24 +08:00
楼上说得对啊，这题目用穷举是简单啊，还需要伪代码吗
|
 |
15
zcjfesky 2018-11-09 14:42:46 +08:00 via Android 1
这是 Kirkman 三元集的 v15 情况， 非同构组合有 7 个
原始穷举法复杂度是 15!的七次方，可以等到地球毁灭 可以考虑深度搜索剪枝，具体参考 sovling the kirksman schoolgirl problem in a few minutes 这篇 ppt，最终剪枝剪到复杂度 20000 的程度 |
Select Language