0

私は自分が取り組んでいる個人的なプロジェクトを持っていて、解決できないように見える問題があります(まあ、私はそれをすぐに解決することはできません)。

私にはx[1..|x|]人々のグループとx要素のグループがあるとしましょう。

ix個のグループ(グループ番号は個人番号用)を作成したいのですiが、各グループにはy異なる要素があります。

例:10人と10個の要素があり、各グループに2つの要素が必要な場合:

|   0   |1  |2  |3  |4  |5  |6  |7  |8  |9  |
|___________________________________________|
|   7   |4  |0  |6  |2  |8  |3  |1  |9  |5  |
|   6   |9  |5  |8  |7  |0  |2  |3  |1  |4  |

一番上の行は人々を表してい(0..9)ます;
各人の下の2つの数字は、彼が持っている要素を示しています。
注意:すべての要素は2回だけ表示されます(それ以上でもそれ以下でもありません)。また、個人番号に要素番号を含めることはできないことに
注意してください。 例:人番号3は要素番号3を持つことはできません。ii

私の問題は、それらのグループを(すばやく)作成する方法です。
これまでに見つけた最善の解決策は、x列とy行を含む行列を作成することです。
サイズの配列を取得してxシャッフルし、マトリックスに挿入できないかどうかを確認します。可能であれば、次の行に移動します。もう一度シャッフルできず、挿入できるかどうかを確認します。

問題は、少数(1000人/要素および各グループで50要素)でもコードが非常に遅いことです。
問題はシャッフルにあります。行(〜13)に一致するものを見つけようとすると、マトリックス内に配置できる行が見つかるまで何度も再シャッフルする必要があります。

誰かがこのことをすばやく行う方法を知っていますか?どんなアイデアでも大歓迎です!!

どうも。

4

2 に答える 2

0

その数の y 要素を完全ではないランダムなグループに配置するたびに、人を反復処理できます。空いているグループの配列を用意し、それらがいっぱいになったら削除し、もちろん現在のグループをランダム選択から除外します。

于 2012-09-17T17:38:58.680 に答える
0

数学的に言えば、固定小数点なしでランダムな順列を生成する必要があります。これは混乱と呼ばれます (ランダム順列が混乱である確率を含む詳細については、こちらを参照してください)。「generate random derangement」または同様のものをグーグルで検索すると、いくつかの実装が見つかります。

于 2012-09-17T18:24:27.943 に答える