無法在合理的運行時間創建隨機組

我有一個我正在工作的個人項目，我有一個我似乎無法解決的問題（好吧，我無法快速解決問題）。無法在合理的運行時間創建隨機組

比方說，我有一組x[1..|x|]人，和一組x元素。

我要創建的X基團（組號i爲人數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);
每個人下面的兩個數字表示他擁有哪些元素。
注意：每個元素只出現兩次（不多也不少）。
另請注意，人員編號i不能包含元素編號i。
例如：人員編號3不能有元素編號3.

我的問題是如何創建這些組（快速）。
到目前爲止，我發現的最佳解決方案是創建一個包含x列和y行的矩陣;
取一個大小爲x的數組，然後對其進行洗牌，然後查看我是否無法將其插入矩陣。如果可以的話，轉到下一行;如果我不能再洗牌，看看現在是否可以插入。

問題是，即使是小數字（1000人/元素和每個組50個元素）代碼是非常緩慢的。
問題在於隨機洗牌，當它試圖找到匹配的行（〜13）時，需要重新洗牌多次，直到找到可以放置在矩陣內的行。

有沒有人知道這件事可以如何快速完成？任何想法都會受到歡迎！

Thx。

來源

2012-09-17 user1677989

他們必須是隨機的嗎？ – Beta

@beta，是的，一個不隨機的解決方案將是做一個轉變，然後我可以很快找到解決方案。我曾想過從範圍1中選擇一組素數... .. | x | （隨機選擇y素數），然後用素數作爲移位參數進行移位。但我不知道結果會是多麼隨意。 – user1677989

您可以迭代人員，每個人將該數字的y個元素放置在未滿的隨機組中。只需要有一個空置組的陣列，當他們填滿時刪除它們，當然也不會從隨機選擇中排除當前組。

來源

2012-09-17 17:38:58 pseudoDust

這並不明顯，這將導致一個統一的隨機洗牌。通常你會發現似乎一致的混洗技術實際上是有偏見的，但除了測試之外，很難確定這一點。例如，請參閱http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle。 – Bitwise

這是行不通的。有5個元素的5個人的想法，你想要在每個組中有2個元素。要放置的元素池（0,0,1,1,2,2,3,3,4,4）現在我遍歷池，從0開始： group＃0： group＃1：0 組＃2：0 組＃3：組＃4：現在1：組＃0：1 組＃1：0 組＃2：0 1 組＃3：組＃4：現在2：組＃0：1 2 組＃1：0 2 組＃2：0 1 組＃3：組＃4：現在我留給{3,3,4,4} ，並且我無法將其放在其他組中。 – user1677989

@雙方你是對的，這可能是有偏見的，很難檢查，雖然...你可以隨機選擇迭代它們的組的順序，但我恐怕這並不能解決問題 – pseudoDust

用數學術語，你想要的是產生一個沒有固定點的隨機置換。這就是所謂的這種被稱爲紊亂的方法（更多細節參見here，包括隨機排列是紊亂的概率）。如果谷歌「生成隨機排列」或類似的東西，你會發現幾個實現。

來源

2012-09-17 18:24:27 Bitwise

問題是不要生成一個沒有固定點的排列，但是我需要生成沒有固定點的y排列。因此，如果我有x個人，我需要創建如下形式：（∀x1，x2∈y＆x1！= x2）=>（ ∀i∈[1 .. | x |] => x1 [i]！= x2 [i]）。 – user1677989

但是，如果您能夠有效地產生一種紊亂，那麼爲什麼只是做這麼多次問題呢？ – Bitwise

@雙方的問題是你不允許在任何組中有重複的情況，即沒有2個錯誤應該把任何給定的數字放在同一個地方。 – pseudoDust

無法在合理的運行時間創建隨機組

回答

相關問題