ペアごとに処理する必要があるデータのセットがあるとします (ペア要素の順序は重要ではないため、これらは組み合わせであり、順列ではありません)。そのために複数のスレッドを利用したいとします。ただし、各データを一度に 1 つのスレッドで処理できるという制約があります。任意のサイズのデータセットに対して、可能な組み合わせの全空間を一度にカバーしながら、データのペアをスレッドに割り当てることができる、優れたパーティショニング戦略を提供するアルゴリズムを探しています。可能な各ペアの処理時間は等しいと仮定します。
たとえば、D0、D1、D2、D3、D4、D5 の 6 つのデータがあるとします。
これらを最適に処理するには、次のようにします。
Thread 1 Thread 2 Thread 3
Time Slot 1 (D0,D5) (D1,D4) (D2,D3)
Time Slot 2 (D0,D4) (D1,D3) (D2,D5)
Time Slot 3 (D0,D3) (D1,D2) (D4,D5)
Time Slot 4 (D0,D2) (D1,D5) (D3,D4)
Time Slot 5 (D0,D1) (D2,D4) (D3,D5)
同様に、8個のデータ: D0、D1、D2、D3、D4、D5、D6、D7
Thread 1 Thread 2 Thread 3 Thread 4
Time Slot 1 (D0,D7) (D1,D6) (D2,D5) (D3,D4)
Time Slot 2 (D0,D6) (D1,D5) (D2,D4) (D3,D7)
Time Slot 3 (D0,D5) (D1,D4) (D2,D3) (D6,D7)
Time Slot 4 (D0,D4) (D1,D3) (D2,D7) (D5,D6)
Time Slot 5 (D0,D3) (D1,D2) (D4,D6) (D5,D7)
Time Slot 6 (D0,D2) (D1,D7) (D3,D6) (D4,D5)
Time Slot 7 (D0,D1) (D2,D6) (D3,D5) (D4,D7)
私は上記を自分の手で考え出しましたが、使用しなければならなかったプロセスはそれぞれでわずかに異なっていたため、より大きなデータ セットに対してこれらを生成するコードに変換するのは難しいようです。これらのペアを適切かつ効率的に生成するアルゴリズムのアイデアはありますか? 解決策を検索しようとしましたが、探している結果を得るために問題をより適切に表現する方法が正確にはわかりません。