combinations - 安排课程的算法

Question

我目前有一个问题，在我大四的时候，我需要从 20 多门可能的课程中选择 5 门选修课。所有这些课程都分配到工作日。我需要开发一个强大的算法来向我展示所有可能的组合，而不会重叠任何课程时间。我的时间有点短，所以我想我会在这里问，这对以后的其他人会有帮助。我最初的想法是尝试 20+ 中的 5 种的所有组合，并删除具有重叠课程的时间表。蛮力解决方案似乎很容易实现。只是出于好奇，这个问题是否还有其他更智能的解决方案？例如，如果我有 1000 多门课程可供选择怎么办？

Answer 1

更快一点可能是选择第一门课程（从 1000 门课程中）并删除所有重叠的课程。然后从剩余的课程中选择第二个课程并再次删除重叠的课程。如果你这样做 5 次，你将有 5 门不重叠的课程。最后一次迭代并不是真正必要的，因为一旦你有 4 门课程，那么剩下的每门课程都不会重叠。

通过回溯，您将获得所有可能的课程组合。此处回溯的一种有效方法是使用 Knuth 提出的舞蹈链接。