算法來隨機填充一個數組而不發生衝突

Question

說我有一個N整數的數組設置爲值'0'，我想選擇一個隨機元素的值爲'0'，並將其值'1'

我該如何有效地做到這一點？

我想出了2個解決方案，但他們看起來相當ineficient

首先解決

int array[N] //init to 0s 
int n //number of 1s we want to add to the array 
int i = 0 
while i < n 
    int a = random(0, N) 
    if array[a] == 0 
     array[a] = 1 
     i++ 
    end if 
end while 

這將是非常低效的，因爲碰撞的概率大陣列

第二個涉及列表中包含剩餘的所有0個位置，我們選擇一個介於0和0之間的隨機數來查找列表中對應於數組中索引的值。 這是一個很大比第一個解決方案更加可靠，因爲操作的數量是有界的，但仍然有N²的最壞情況的複雜性，如果我們要填補陣列完全

Answer 1

你的第二個解決方案實際上是一個良好的開端。我假設它涉及每次更改後重建位置列表，如果要填充整個數組，則使其成爲O（N²）。但是，您不需要每次重建列表。既然您想要填充數組，您可以使用隨機順序並相應地選擇剩餘的位置。

作爲一個例子，採取以下陣列（大小7，而不是最初全零的）：[0, 0, 1, 0, 1, 1, 0]

一旦你建立零位置，這裏[0, 1, 3, 6]的列表，只需將它洗得到一個隨機排序。然後按照職位給定的順序填寫數組。

例如，如果洗牌給[3, 1, 6, 0]，那麼你就可以填充數組，像這樣：

[0, 0, 1, 0, 1, 1, 0] <- initial configuration 
[0, 0, 1, 1, 1, 1, 0] <- First, position 3 
[0, 1, 1, 1, 1, 1, 0] <- Second, position 1 
[0, 1, 1, 1, 1, 1, 1] <- etc. 
[1, 1, 1, 1, 1, 1, 1] 

如果數組最初用零填充，那麼它更容易。您的初始列表是從0到N（數組大小）的整數列表。隨機播放並應用相同的過程。

如果你不想填充整個數組，你仍然需要構建整個列表，但是在洗牌後可以截斷它（這意味着在某點之後停止填充數組）。

當然，這個解決方案要求數組在每一步之間不會改變。

Answer 2

與 n者和 N-n

您可以填寫陣列零和隨機洗牌。

Fisher-Yates shuffle具有線性複雜：

for i from N−1 downto 1 do 
    j ← random integer such that 0 ≤ j ≤ i 
    exchange a[j] and a[i]