N^2 の数値と N 個のビンのセットがあります。各ビンには、割り当てられたセットからの N 個の番号があると想定されています。私が直面している問題は、数値の各ペアが同じビンを一度だけ共有できるという制約を満たす、数値をビンにマップする一連の分布を見つけることです。
分布は、各行がビンを表す NxN 行列でうまく表現できます。次に問題は、行列の要素の順列のセットを見つけることです。この順列では、数値の各ペアが同じ行を 1 回だけ共有します。どの行であるかは関係ありませんが、2 つの番号が両方とも同じ番号に割り当てられているだけです。
N=8 の制約を満たす 3 つの順列のセットの例:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63
0 8 16 24 32 40 48 56 1 9 17 25 33 41 49 57 2 10 18 26 34 42 50 58 3 11 19 27 35 43 51 59 4 12 20 28 36 44 52 60 5 13 21 29 37 45 53 61 6 14 22 30 38 46 54 62 7 15 23 31 39 47 55 63
0 9 18 27 36 45 54 63 1 10 19 28 37 46 55 56 2 11 20 29 38 47 48 57 3 12 21 30 39 40 49 58 4 13 22 31 32 41 50 59 5 14 23 24 33 42 51 60 6 15 16 25 34 43 52 61 7 8 17 26 35 44 53 62
上記のセットに属さない順列:
0 10 20 30 32 42 52 62 1 11 21 31 33 43 53 63 2 12 22 24 34 44 54 56 3 13 23 25 35 45 55 57 4 14 16 26 36 46 48 58 5 15 17 27 37 47 49 59 6 8 18 28 38 40 50 60 7 9 19 29 39 41 51 61
2 番目の順列との複数の衝突が原因で、たとえば、両方とも 0 と 32 が 1 つの行でペアになっているためです。
3 つ列挙するのは簡単です。1 つの任意の順列、その転置、および行が前の行列の対角線で構成される行列で構成されます。
ただし、より多くのセットを作成する方法が見つかりません。それは非常に複雑な問題か、解決策が明らかでない単純な問題のいずれかのようです。いずれにせよ、誰かが N=8 の場合に合理的な時間内に解決する方法を知っていたり、問題の適切な学術名を特定したりしてくれれば、私はそれをググることができてありがたいです.
何に役立つのか疑問に思っている方のために説明すると、64 の宛先にトラフィックを提供する、8 つのバッファーを持つクロスバー スイッチのスケジューリング アルゴリズムを探しています。スケジューリング アルゴリズムのこの部分は、入力トラフィックに依存せず、多数の固定配線された宛先バッファ マッピング間を周期的に切り替えます。目標は、宛先アドレスの各ペアが循環期間中に一度だけ同じバッファーを競合するようにし、その期間の長さを最大化することです。言い換えれば、アドレスの各ペアが同じバッファーをめぐって競合することができるだけ少なくなるようにするためです。
編集：
ここに私が持っているいくつかのコードがあります。 コード
貪欲です。通常、3 番目の順列を見つけた後に終了します。しかし、問題を満たす少なくとも N 個の順列のセットが存在する必要があります。
別の方法では、順列 I を選択する際に順列 (I+1..N) を探して、順列 I が最大数の順列からなる解の一部であるかどうかを確認する必要があります。これには、各ステップでチェックするすべての順列を列挙する必要があり、法外なコストがかかります。