一个算法题目：女学生散步问题

[zemora]

这个问题叫做 Kirkman's Schoolgirl Problem，即某学校有十五名女生，她们经常每天三人一行、共组成五行去散步，问要怎样安排才能使得在一周的时间里，任何两个女生恰好在同一行中散步一次？

找出一种来不难，网上有很多，我在想怎么能罗列出所有的解法来。不知道大家有什么好办法没有？

[Deville]

女生长得好看么；
有微信号么；
哪个学校的；
确定都是女生并没有混入女装大佬么？

[alikesi]

@Deville 充分考虑程序边界条件，优秀。

[Deville]

@alikesi 其实想想这道题还是挺有趣的喔

[coderluan]

直接设置 15 个变量，然后暴力枚举所有情况，最后再挨个检查是否符合要求，没要求复杂度的前提下，暴力枚举就是最好的算法。

[mathzhaoliang]

@coderluan 伪代码呢？ talk is cheap, show me the code.

[dikT]


[Fulcrum]

像一个复杂的指派规划。。。

[coderluan]

@mathzhaoliang

"talk is cheap, show me the code." 这话是用来解决技术争论的，你没提自己的观点和反对意见，也就是没争论。
现在的情况，是别人帮忙提供解决问题的思路，你却指责对方不给代码，这是什么行为，我不就不说了。
希望你只是不小心滥用了词语。

[ryd994]

第一列 A 不动，第二列 B 每次 shift1，第三列 C 每次 shift2
5 天后，所有的 A 都和所有的 B 并排过，所有的 B 都和所有的 C 并排过。这个应该不难证。
剩下 AC 并排关系。A1 和 B135 并排然后绕回来 24 正好
完成

[ryd994]

等等，还漏了 ABC 各自内部，我再想想

[kenv07]

楼上说暴力枚举的，15 的阶乘等于 1,307,674,368,000，所以其实可行就是要花点时间

[wdv2ly]

楼上说得对啊，这题目用穷举是简单啊，还需要伪代码吗

[zemora]

@wdv2ly 要是穷举就行，还要算法做什么。Leetcode 还有时间限制呢。

[wdv2ly]

@zemora 穷举也是算法的一种啊。你只说找出所有组合，又没说有其它要求，那肯定直接穷举咯。

[zcjfesky]

这是 Kirkman 三元集的 v15 情况， 非同构组合有 7 个

原始穷举法复杂度是 15!的七次方，可以等到地球毁灭
可以考虑深度搜索剪枝，具体参考 sovling the kirksman schoolgirl problem in a few minutes 这篇 ppt，最终剪枝剪到复杂度 20000 的程度