生成隨機整數與差約束

Question

我有以下問題：

產生m個由範圍爲0-N，其中N >> M，且其中沒有對具有差小於K. 均勻隨機整數其中M >> K 。

目前我能想到的最好的方法是維護一個排序列表，然後確定當前生成的整數的下界，並用下方和上方元素進行測試，如果可以插入元素之間。這是複雜的O（nlogn）。

會碰巧有更高效的算法嗎？

的問題的一個例子：

生成零和1億，其中任何兩個整數之間的差不小於1000

全面的方式來解決，這將是到1000個之間的均勻隨機整數：

1. 確定的正選擇-M滿足約束的所有組合，讓稱爲它設置X
2. 在範圍[0，選擇均勻隨機整數i，| X |）。
3. 從X中選擇第i個組合作爲結果。

當n選擇m很大時，此解決方案有問題，因爲枚舉和存儲所有可能的組合將會非常昂貴。因此尋求高效的在線生成解決方案。

注：下面是一個C++實現由提供的解決方案的十五邊形

std::vector<int> generate_random(const int n, const int m, const int k) 
{ 
    if ((n < m) || (m < k)) 
     return std::vector<int>(); 

    std::random_device source; 
    std::mt19937 generator(source()); 
    std::uniform_int_distribution<> distribution(0, n - (m - 1) * k); 

    std::vector<int> result_list; 
    result_list.reserve(m); 

    for (int i = 0; i < m; ++i) 
    { 
     result_list.push_back(distribution(generator)); 
    } 

    std::sort(std::begin(result_list),std::end(result_list)); 

    for (int i = 0; i < m; ++i) 
    { 
     result_list[i] += (i * k); 
    } 

    return result_list; 
} 

http://ideone.com/KOeR4R

。

Answer 1

爲什麼不能做到這一點：

for (int i = 0; i < M; ++i) { 
    pick a random number between K and N/M 
    add this number to (N/M)* i; 

現在你有m個隨機數字，沿ñ均勻分佈，所有這些都至少K.這是一個在O（n）的時間差。作爲額外的獎勵，它已經排序。 :-)

編輯：

實際上， 「選擇一個隨機數」 部分不應該K和N/M之間，但min(K, [K - (N/M * i - previous value)])之間。這將確保差異至少爲K，並且不排除不應忽略的值。

第二編輯：

好，第一種情況下不應該是K和N/M之間 - 它應該是0和N/M之間。就像您在接近N/M *邊界時需要特殊外殼一樣，我們需要特殊的初始套管。

除此之外，你在評論中提出的問題是公平的代表性，你是對的。當我的僞代碼被提交時，它現在完全忽略了N/M * M和N之間的過量。這是另一個邊緣案例;只需更改最後一個範圍的隨機值。

現在，在這種情況下，您的分配將在最後一個範圍內有所不同。由於你有更多的號碼，每個號碼的機會比所有其他範圍的機會略少。我的理解是，因爲你使用「>>」，這不應該真正影響分佈，即樣本集中的大小差異應該是標稱的。但是如果你想讓它更公平，你可以在每個範圍內平均分配多餘的錢。這使得你的初始範圍計算更復雜 - 你必須根據M除以多少餘數來增加每個範圍。

有很多特殊情況需要注意，但它們都能夠被處理。我保持這個僞代碼非常基本，以確保總體概念清晰。如果沒有別的，它應該是一個很好的起點。

第三個也是最後編輯：

對於那些擔心分佈具有強制均勻性，我仍然聲稱沒有什麼說，它不能。選擇均勻分佈在每個分段中。有一個線性的方法來保持它的不平衡，但也有一個折衷：如果選擇一個非常高的值（對於非常大的N應該不太可能），那麼所有其他值都受到限制：

int prevValue = 0; 
int maxRange; 
for (int i = 0; i < M; ++i) { 
    maxRange = N - (((M - 1) - i) * K) - prevValue; 
    int nextValue = random(0, maxRange); 
    prevValue += nextValue; 
    store previous value; 
    prevValue += K; 
} 

這仍然是線性和隨機的，並允許不均勻性，但更大的prevValue得到，其他數字變得越受約束。就個人而言，我更喜歡我的第二個編輯答案，但這是一個可用的選項，如果足夠大，N很可能會滿足所有發佈的要求。

想想吧，這裏有一個其他的想法。它需要更多的數據維護，但仍然是O（M），並且可能是最公平的分佈：

您需要做的是維護有效數據範圍的向量和概率尺度的向量。有效的數據範圍只是K仍然有效的高低值列表。這個想法是你首先使用縮放的概率來選擇一個隨機的數據範圍，然後你隨機選擇一個範圍內的值。您可以刪除舊的有效數據範圍，並將其替換爲0,1或2個新的數據範圍，具體取決於有多少個仍然有效。除了處理加權概率O（M），在循環中執行M次，所有這些操作都是恆定時間，因此總數應該是O（M^2），這應該比O（NlogN）好得多，因爲N >> M.

而不是僞代碼，讓我用OP原來的工作，例如一個例子：

• 0次迭代：有效的數據範圍爲[0 ... 100Mill]，重量爲這個範圍是1.0。
• 第一次迭代：隨機選取一個元素向量中的一個元素，然後隨機選取該範圍中的一個元素。
  • 如果元素是，例如， 12345678，然後我們刪除[0 ... 100Mill]並用[0 ... 12344678]和[12346678 ... 100Mill]
  • 替換它。 500，然後我們刪除[0 ... 100Mill]並用[1500 ... 100Mill]替換它，因爲[0 ... 500]不再是有效範圍。我們唯一一次將其替換爲0的範圍是不太可能的，因爲您只有一個範圍，並且它被選中。 （在這種情況下，連續3個數字彼此完全相距K）。
  • 範圍的權重是它們在總長度上的長度e。G。 12344678 /（12344678 +（100Mill - 12346678））和（100Mill - 12346678）/（12344678 +（100Mill - 12346678））

在接下來的迭代中，你做同樣的事情：隨機挑選一個數字在0和1之間，並確定哪些範圍落入。然後在該範圍內隨機選取一個數字，並替換您的範圍和比例。當它完成時，我們不再在O（M）中動作，但是我們仍然只依賴於M的時間而不是N.這實際上是均勻和公平的分佈。

希望這些想法之一適合你！

Answer 2

編輯：我調整了要求創建有序序列的文本，每個都有相同的概率。

爲i=0..M-1創建隨機數a_i而不重複。對它們排序。然後創建一個數字

b_i=a_i + i*(K-1) 

鑑於建設，這些b_i具有所需缺口數字，因爲a_i已經有至少1差距。爲確保這些b值完全覆蓋了要求的範圍[1..N]，您必須確保a_i從[1..N-(M-1)*(K-1)]範圍內挑選。這樣你就可以得到真正獨立的數字。那麼，考慮到所需的差距，儘可能獨立。由於排序，您可以再次獲得O（M log M）性能，但這應該不會太差。排序通常非常快。在Python它看起來像這樣：

import random 
def random_list(N, M, K): 
    s = set() 
    while len(s) < M: 
     s.add(random.randint(1, N-(M-1)*(K-1))) 

    res = sorted(s) 

    for i in range(M): 
     res[i] += i * (K-1) 

    return res 

Answer 3

第一關：這將是表明還有的(M+1)之間的一一對應的嘗試 - compositions（有輕微修改，我們將允許加數是0）的價值N - (M-1)*K和您的問題的有效解決方案。之後，我們只需要隨機選擇一種組合物並應用雙射。

---

雙向注入：

讓

那麼X _我形成M+1組成 - ·（具有允許0加數）的值的左側（通知那個x _i不一定是單調的壓痕！）。

由此我們得到一個有效的解決方案

通過設置值M _我如下：

我們看到是m _我之間的距離和m _{i + 1}至少爲K和m _M最多爲N（比較我們開始使用的組合物的選擇）。這意味着每個滿足上述條件的組合都會爲您的問題定義一個有效的解決方案。 （你會發現，我們只使用x _中號作爲一種方法，使之變成正確的，我們不使用它的m個_我建設。）

一看就知道給出一個雙射，我們需要看到這個構造可以顛倒過來;爲了這個目的，讓

是一個給定的解決方案滿足您的條件。爲了得到這個從構建組成，如下定義X _我：

現在首先，所有的X _我至少0，所以這是正常的。看到他們形成有效成分（再次，每x _我允許爲0）上面給出的值，可以考慮：

第三平等如下，因爲我們有這樣的伸縮總和是幾乎消除了所有的m _i。

所以我們已經看到，描述的結構給出了所描述的N - (M-1)*K的組合與您的問題的有效解決方案之間的雙射。我們現在要做的就是隨機挑選其中一種組合物，然後使用這種結構來獲得解決方案。

---

採摘的組合物均勻地隨機

每一個都可以以下面的方式被唯一標識，所述的組合物的（比較this用於說明）：儲備N - (M-1)*K空間用於該值的一元表示法，和另一個M空格用於M逗號。我們得到一個(M+1) - 組成N - (M-1)*K通過選擇N - (M-1)*K + M空間的M，把逗號放在那裏，並填寫其餘的|。然後讓X 是第一個逗號之前的|數，X _{M + 1}的|最後一個逗號之後的數量，並且所有其它的X _我的|逗號i和i+1之間的數量。因此，我們所要做的就是隨機選擇一個整數區間[1; N - (M-1)*K + M]的元素子集，我們可以使用例如Fisher-Yates shuffle在O(N + M log M)（我們需要對M分隔符進行排序以構建組合） M*K需要在O(N)存在任何解決方案。因此，如果N至少以對數因子大於M，那麼這在N中是線性的。

---

注：@DavidEisenstat建議，有更多的空間採摘間隔M - 元素的子集的有效途徑;我不知道有任何恐懼。

---

你可以做簡單的輸入驗證我們從N ≥ (M-1) * K以上建設得到得到一個錯誤驗證算法出這一點，所有這三個值至少1（或0，如果定義空作爲該案件的有效解決方案）。