生成非重複的隨機數

我想在C中創建一個函數。它將返回一個範圍爲N的隨機整數，如下所示： - rand（）％N; 但事情是我想跟蹤唯一性。我不希望數字重複。但我也可以通過創建一個數組並將其中生成的整數複製來做到這一點。如： - array[count] = rand() % N;並每次檢查生成的數字是否已經在其中。（只需在數組[]中搜索它）;這是一個簡單的方法，但是一個正確的方法。它會採取許多如果和爲了;爲此工作。這是我能想到的最好的。生成非重複的隨機數

的事情是，我想這個問題的最佳/優化的解決方案。什麼將是最有效的方式來做到這一點？

允許明確一些事情： - 我想從一個NSArray中，始終是唯一坐落在一個UILabel一些文本。我的NSArray從Plist獲取數據，而我的Plist有超過1000個條目。如果我想這樣做很多次，它會影響性能，所以我想要一些有效的方式來做到這一點。

來源

2011-12-18 SAQIBZAFAR

如果它保證沒有重複不再是隨機的，是不是邏輯？ – 2011-12-18 19:47:18

同一句子中的「隨機」和「唯一」不屬於。你試圖解決的問題究竟是什麼？ – Jon 2011-12-18 19:47:27

可以說我想填充一個數組，直到100的隨機數，或另一個iPhone開發的例子是，我從1000個對象的NSArray標籤中顯示隨機對象。 – SAQIBZAFAR 2011-12-18 19:50:59

這聽起來像你想要的是真正的數字1..N的隨機排列。所以，用一個連續的整數1..N填充一個數組，然後對數組進行洗牌。有well known algorithms for shuffling，你可以查找。

來源

2011-12-18 20:17:10 Caleb

使用某種散列表來存儲已經生成的號碼並快速檢查已經看到的號碼。我不知道你在做什麼，但是因爲你需要獨特的蘭特，我想你正試圖對一個有限集進行排列，如果是這樣的話，看一下Shuffling Algorithms。

來源

2011-12-18 19:48:11

肯定是一種可能性.. – SAQIBZAFAR 2011-12-18 19:53:02

而不是一個數組，你可以使用超快速高效的bloom filter。如果你正在生成大量的數字，這將比在數組中循環更快。

來源

2011-12-18 19:52:54

謝謝，我必須爲iPhone設計它還是有一個類爲我實現它，我可以直接使用它？ – SAQIBZAFAR 2011-12-18 19:57:28

Apple沒有提供這樣的構造。雖然可能有圖書館可以在某處使用。我從來沒有使用過自己，所以不能提供更多建議。 – 2011-12-18 20:35:35

四個選項，所有這一切都是Ø（1）在內存和時間：

只是增加一個全局計數器。既然你想要唯一性，無論如何你都不能生成隨機數。
從一個足夠大的集合中生成一個數字，以至於很難重複一個數字。 64位足以支持應用內唯一性;全局唯一性足夠128位。這是UUID的工作方式。
如果選項1對您來說不夠「隨機」，則使用全局（32位）計數器的CRC-32散列值。 N比特整數與它們的CRC-N之間有1對1的映射（雙射），所以唯一性仍將得到保證。
使用Linear Feedback Shift Register生成數字。這些是N位計數器，它們看起來是「隨機的」（儘管顯然是確定性的）模式。出於您的目的，這基本上是選項3的適度更快的版本。

來源

2011-12-19 19:00:54

所描述的算法非常糟糕，因爲它會針對每個新條目搜索新數組。這意味着隨着數組的增長，它必須搜索越來越多的數據，更糟糕的是，隨着剩餘數量的減少，它將最終循環更多。

例如，如果您有一個1 ... 10的列表，那麼當您填充了八個項目時，現在只剩下兩個項目（比如說7和9），每次生成一個隨機數字時在80％的時間內生成非唯一編號，並且必須在檢測到重複項之前掃描至少六個條目。

有可能是一些在一些圖書館，甚至更好的方法，但比在問題的更好的辦法是創建項目的（鏈接）列表中，隨機挑選一個，刪除它，並將它添加到新的名單。這樣，每次你隨機挑選一個，它就會保證是唯一的，因爲所使用的不再在池中。

來源

2016-01-13 01:36:59 Synetech

生成非重複的隨機數

回答

相關問題