構建一個非序列的數字列表（從很大的範圍）

我需要創建一個適合範圍的非序列數字列表。例如，我需要生成一個從1到1百萬的數字列表，並確保數字中的非數字按順序排列，它們完全被洗牌。我想我的第一個問題是，有沒有什麼好的算法可以幫助以及如何最好地實現這一點。構建一個非序列的數字列表（從很大的範圍）

我目前不確定實現的最佳方式，無論是通過ac＃console應用程序，它將吐出XML文件中的數字或數據庫中的數字，將數字吐出到一個表或一組表中，但這確實是次要的，因爲實際上正在制定出「洗牌」這組數字的最佳方式。

任何意見傢伙？

Rob

來源

2009-12-10 Modika

「完全洗牌」並不意味着兩個數字不能連續。創建隨機唯一數字列表的一個可能性是它們都將按順序排列。你能給個例子嗎？ – Carra 2009-12-10 16:39:12

您是否需要「非順序」？

你可以輕鬆地從各個生成隨機數的列表，Random類：

Random rnd1 = new Random(); 
List<int> largeList = new List<int>(); 

for (int i = 0, i < largeNumber, i++) 
{ 
    largeList.Add(rnd1.Next(1, 1000001); 
}

編輯補充

不可否認的Durstenfeld算法（費舍爾的現代版顯然yates shuffle）要快得多：

var fisherYates = new List<int>(upperBound); 
for (int i = 0; i < upperBound; i++) 
{ 
    fisherYates.Add(i); 
} 

int n = upperBound; 

while (n > 1) 
{ 
    n--; 
    int k = rnd.Next(n + 1); 
    int temp = fisherYates[k]; 
    fisherYates[k] = fisherYates[n]; 
    fisherYates[n] = temp; 
}

對於範圍1到10000做一個蠻力「找到一個我還沒用過的隨機數」大約需要4-5秒，而這大約需要0.001秒。

道具爲Greg Hewgill爲鏈接。

來源

2009-12-10 15:05:43

如果您想確保沒有數字是連續的，您可以使用z的解決方案，並將先前生成的隨機數保存在局部變量中。然後將其與下一個生成的號碼進行比較，並根據需要接受或拒絕該號碼。 – Ray 2009-12-10 15:11:35

呵呵，正在編寫我的程序並同時進行測試 - 如果您不關心重複的話，速度會更快。 – 2009-12-10 15:32:12

嗨Z，感謝您的代碼，我很樂意不在乎重複，但我需要數字列表，沒有重複。 – Modika 2009-12-10 16:42:23

「完全洗牌」是一個非常誤解的術語。欺詐專家在檢查什麼應該是「隨機」數據時使用的一個欺騙手段是觀察沒有重複值的情況（例如3743 *** 88 *** 123，因爲以真正隨機的順序，沒有這樣一對的機會非常低......你想要做什麼？你究竟是什麼意思，「完全洗牌」？如果你的意思是隨機數字序列，那麼只需使用CLR中的Random類生成隨機數0和1M ...儘可能多的，因爲你需要...

來源

2009-12-10 15:07:08

幸福感，你可以像這樣的東西去（假設你希望每個號碼只有一次）：

DECLARE @intFrom int 
DECLARE @intTo int 
DECLARE @tblList table (_id uniqueidentifier, _number int) 

SET @intFrom = 0 
SET @intTo = 1000000 

WHILE (@intFrom < @intTo) 
BEGIN 
    INSERT INTO @tblList 
    SELECT  NewID(), @intFrom 

    SET @intFrom = @intFrom + 1 
END 

SELECT * 
FROM  @tblList 
ORDER BY _id

免責聲明：我沒有我沒有測試過這個，因爲我沒有m個SQL Server現在處置。

來源

2009-12-10 15:11:18

小細節，顛倒INSERT INTO select子句的項目列表 – Sparky 2009-12-10 15:18:25

當然你是對的，謝謝！我修好了。 – 2009-12-10 15:20:34

這裏是一個C＃的功能，讓你開始：

public IEnumerable<int> GetRandomSequence(int max) 
{ 
    var r = new Random(); 
    while (true) 
    { 
     yield return r.GetNext(max); 
    } 
}

調用它像這樣得到一個萬個號碼範圍0-9999999：

var numbers = GetRandomSequence(9999999).Take(1000000);

爲排列，或者如果你不」 t想要允許重複，看看Enumerable.GetRange()（這將給你一個連續的有序序列），並使用Fisher-Yates（或Knuth）shuffle算法（你可以找到所有的地方）。

來源

2009-12-10 15:12:34

請注意，您可以找到Fisher-Yates shuffle算法*實施不當。我編輯了不止一本「自學C＃」書籍，其中有不正確的實現。不要盲目信任它;自己閱讀以確保它實際上實現了真正的算法。 – 2009-12-10 15:49:48

首先，如果數字的無是按順序然後序列中的每數必須比其前身以下。具有該屬性的序列從大到小排序！顯然這不是你想要的。（或者也許你根本不想要5,6,7格式的任何子序列？但是6,8,20就可以了？）

要正確回答您的問題，我們需要了解有關問題空間的更多信息。的事情，我想知道：

1）等於範圍的大小，比該序列的大小，或者更小？也就是說，你會問1到10之間的10個數字，1到10之間的5個數字還是1到10之間的50個數字？

2）它是可以接受的序列與包含重複？（如果項的序列中的數是大於該範圍，則顯然是肯定的。）

3）什麼是被用於隨機性？大多數隨機數發生器只是僞隨機的;一個聰明的攻擊者可以通過了解前面的那個來推斷下一個「隨機」數字。例如，如果你從52副牌中生成一系列五張牌作爲一手牌，那麼你需要非常強的隨機性;你不希望球員能夠推斷他們手中的對手。

來源

2009-12-10 15:14:00

我明白了，你想從1獲得lenth 1mio的所有數的隨機陣列1mio。沒有重複，是嗎？

你應該建立與數字陣列範圍從1到1mio。然後開始洗牌。但它可能發生（這是真正的隨機性），兩個或更多的數字是連續的。

看一看here

來源

2009-12-10 15:15:28 tanascius

+1如果你需要隨機化一個已知的集合，那麼這是如何做到這一點。 – Andrew 2009-12-10 15:24:08

我想在此引用史蒂夫喬布斯的話，引用iPod上的一個首選項，以減少來自同一作者的兩首歌曲的可能性，因爲有人沒有發現它足夠隨意：「這實際上不那麼隨意」。 – Agos 2009-12-10 16:08:38

這可能會得到你所需要的：

1）填充，從而號碼列表。如果您的範圍是1-x，它將如下所示： [1,2,4,5,6,7,8,9，...，x]

2）遍歷列表x次，每次選擇從0到您的列表的長度的隨機數 - ）1.

3使用此選擇編號，以從列表中選擇對應的元件，並且該號碼添加到輸出列表。

4）刪除剛剛從列表中選擇的元素。沖洗，重複。

這對於任何範圍的數字，這樣開始的不只是列出了工作1或0的僞代碼如下所示：

nums = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 
shuffled_nums = [] 
for i in range(0, len(nums)): 
    random_index = rand(0,len(nums)) 
    shuffled_nums.add(nums[random_index]) 
    del(nums[random_index])

來源

2009-12-10 15:19:42

請注意，對於列表的許多實現，從中間刪除一個元素的大小是O（n）。這會使你的算法O（n^2），這可能是不可行的，因爲我們已經知道範圍將達到一百萬大小。 – 2009-12-10 15:45:03

好的。謝謝。 – 2009-12-10 16:17:17

構建一個非序列的數字列表（從很大的範圍）

回答

相關問題