填充間隔的隨機數生成器

如何實現一個隨機數生成器，給定間隔（隨機）生成該間隔中的所有數字，而沒有任何重複？填充間隔的隨機數生成器

它應該消耗盡可能少的時間和內存。

實施例在剛剛發明C＃-ruby肥胖型僞代碼：

interval = new Interval(0,9) 
rg = new RandomGenerator(interval); 
count = interval.Count // equals 10 
count.times.do{ 
    print rg.GetNext() + " " 
}

這應該輸出類似：

1 4 3 2 7 5 0 9 8 6

來源

2010-02-17 Cristi Diaconescu

裝滿間隔的陣列，然後將它洗。

混洗N個元素數組的標準方法是從0到N-1（比如R）之間選擇一個隨機數，並用項[N]交換項目[R]。然後從N中減去一個，然後重複，直到你達到N = 1。

來源

2010-02-17 12:58:41

值得指出的是，「標準」洗牌你提的是費雪耶茨-Durstenfeld算法：http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_modern_algorithm – LukeH 2010-02-17 13:14:17

一個建議，但它的內存密集型：

發電機建立在區間的所有號碼的列表，然後洗牌它。

來源

2010-02-17 12:59:09

採取所有號碼的間隔，把它們列出/陣列
Shuffle列表/陣列
循環列表/陣列

來源

2010-02-17 12:59:46

一種方法是產生一個有序列表過（0-9）在你的例子。

然後使用隨機函數從列表中選擇一個項目。從原始列表中刪除項目並將其添加到新項目的尾部。

當原始列表爲空時，過程完成。

輸出新的列表。

來源

2010-02-17 13:00:11 ChrisF

偶爾有用的替代洗牌方法是使用可下標集容器。在每一步中，選擇一個隨機數0 < = n < count。從集合中提取第n個項目。

主要問題是典型的容器無法有效地處理這個問題。我已經將它用於位矢量，但只有在可能的最大成員相當小的情況下才能正常工作，這是由於要找到第n個設置位所需的位向量的線性掃描。

99％的時間，最好的方法是洗牌，如其他人所建議的。

編輯

我錯過了一個事實，即一個簡單的數組是一個很好的「設置」數據結構 - 不要問我爲什麼，我曾經使用過它。「技巧」是你不關心數組中的項是否被排序。在每一步中，您隨機選擇一個並提取它。要填充空槽（不必將平均一半的項目移動一步），只需將當前最終項目在恆定時間內移動到空槽中，然後將數組的大小減小一。

例如...

class remaining_items_queue 
{ 
    private: 
    std::vector<int> m_Items; 

    public: 
    ... 

    bool Extract (int &p_Item); // return false if items already exhausted 
}; 

bool remaining_items_queue::Extract (int &p_Item) 
{ 
    if (m_Items.size() == 0) return false; 

    int l_Random = Random_Num (m_Items.size()); 
    // Random_Num written to give 0 <= result < parameter 

    p_Item = m_Items [l_Random]; 

    m_Items [l_Random] = m_Items.back(); 
    m_Items.pop_back(); 
}

訣竅是得到一個隨機數發生器，讓（具有相當均勻的分佈）數取值範圍爲0到n-1，其中n每次都是潛在的不同。大多數標準隨機發生器給出一個固定的範圍雖然下面DOES NOT給均勻分佈，它往往是不夠好......

int Random_Num (int p) 
{ 
    return (std::rand() % p); 
}

的std ::蘭特範圍爲0 < = X < RAND_MAX，其中RAND_MAX是實現定義返回隨機值。

來源

2010-02-17 13:06:49 Steve314

非常有效的方式混洗數的數組，其中每個索引是唯一的來自圖像處理和應用等像素溶解技術時使用。

基本上你開始有序2D陣列，然後轉移列和行。這些排列方式很容易實現，甚至可以有一個確切的方法在n個排列後在x，y處產生結果值。

的基本技術，在一個3x3格描述：

1）先從一個有序列表，每個號碼可以只出現一次

0 1 2 
3 4 5 
6 7 8

2）選擇您要洗牌行/列，提前一步。在這種情況下，我正在向右移動第二行。

0 1 2 
5 3 4 
6 7 8

3）選擇您想要隨機播放的行/列...我將第二列向下拖動一次。

0 7 2 
5 1 4 
6 3 8

4）挑...例如，第一行，一個在左邊。

2 0 7 
5 1 4 
6 3 8

您可以隨意重複這些步驟。您也可以在一維數組上進行這種轉換。所以你的結果現在是[2，0，7，5，1，4，6，3，8]。

來源

2010-02-17 13:13:53

這種情況以前也上來了。嘗試使用linear feedback shift register。

來源

2010-02-17 13:18:00 plinth

您可以使用linear congruential generator與隨機，但這樣它產生的整段時間選擇的參數。您需要小心，因爲隨機數字的質量可能不好，這取決於參數。

來源

2011-11-02 07:18:25 starblue

填充間隔的隨機數生成器

回答

相關問題