私の甥は、コーヒーと会話のためにビジネスの人々を結びつける新しいビジネスを持っています。椅子取り椅子のようなものです。一定の時間が経過すると、全員が別のテーブルに移動します。アイデアは、誰もが一人一人と話す機会を持たなければならないということです. 彼は、16 人で、全員が 5 回移動する 4 つのテーブルでそれを行う方法を見つけようとしています。
それを行うためのアルゴリズムを理解したかったのですが、最初に想像したよりもはるかに難しい問題であることがわかりました。簡単にするために、6人で3つのテーブルでそれを行う方法を考え出しました. 次のように表すことができます。
Step 1: (1, 2), (3, 4), (5, 6)
Step 2: (1, 3), (2, 5), (4, 6)
Step 3: (1, 4), (2, 6), (3, 5)
Step 4: (1, 5), (2, 4), (3, 6)
Step 5: (1, 6), (2, 3), (4, 5)
あまり効率的ではない 1 つの可能性は、考えられるすべての組み合わせを生成し、相互に排他的な組み合わせを排除することです。ただし、奇妙な組み合わせでは、それは不可能です。たとえば、テーブルが 2 つしかない 6 人がいる場合、2 人が同じテーブルに複数回座っていることになります。もちろん、アルゴリズムの考え方は、最短のステップ数で全員が少なくとも 1 回は会うようにすることです。