combinations - コースをスケジュールするアルゴリズム

Question

私は現在、私のシニア年のために、20以上の可能なコースから5つの選択科目を選択する必要があるという問題を抱えています。これらのコースはすべて平日に配布されます。コース時間を重複させることなく、考えられるすべての組み合わせを表示するための堅牢なアルゴリズムを開発する必要があります。少し時間が足りないので、ここで聞いてみたら、将来は他の人の役に立つと思いました。私の当初のアイデアは、20以上のうち5つをすべて組み合わせて試して、コースが重複しているスケジュールを削除することでした。強引なソリューションは実装が簡単なようです。好奇心から、この問題に対する別のよりインテリジェントな解決策はありますか？たとえば、1000以上のコースから選択できる場合はどうなりますか？

Answer 1

最初のコース (1000 のうち) を選択し、重複するすべてのコースを削除すると、少し速くなる可能性があります。次に、残りのコースから 2 番目のコースを選択し、重複するコースを再度削除します。それを5回やると、重ならないコースが5つできます。4 つのコースを作成すると、残りのすべてのコースが重複しないため、最後の反復は実際には必要ありません。

バックトラックすると、可能なすべてのコースの組み合わせが得られます。ここで後戻りする効率的な方法は、Knuth によって提案されたダンス リンクを使用することです。