隨機將元素放入N桶

Question

我有一袋100土豆。我需要將土豆分成N個桶。在每桶中，我必須有15到60個土豆。

很明顯，我需要一步一步的解決方案，使其成爲代碼。

我有迄今爲止的最佳方式：

桶的最低數目：100/60 = 1（40）=>輪它=> 2
桶的最大數目：100/15 = 6 （10）=>輪下來=> 6

所以可以有至少2和最多6個桶。現在我們選擇一個隨機數（因爲我只需要一個解決方案，而不是全部）。

讓我們挑選每桶3.
土豆：100/3 = 33（1）
剷鬥：33，33，34

現在這裏是棘手的部分。雖然這是對原始問題的解決方案，但它不適用於我，因爲我需要的數字比這更隨機。在這個問題的條件是15-60，但在這裏我們只得到33-34，這是我所需要的太統一。

從這裏的解決方案之一可能是開始從每個桶中添加和減去數字。可能做10次左右的迭代，但我認爲必須有更好的方法來做到這一點。

任何想法？

Answer 1

首先，分配所需的最小數量。在你的例子中，將15放入每個桶中。如果你有3個桶，你可以將45個放入3個桶中。剩餘（R）：55.每個桶（C1，C2，C3）的剩餘容量：45。

選擇一個數字k（見關於如何選擇k的腳註）。如果它大於R，則將其設置爲R（k = min（k，R））。隨機選擇一個桶。如果Ci小於，則k將k設置爲Ci（k = min（k，Ci））。現在把k土豆放入桶中。更新R和Ci（R = R-k，Ci = Ci-k）。重複此操作，直到所有土豆完成（R = 0）。

腳註：挑選ķ

您可以設定k = 1時，或選擇從任何適當分佈K（例如：選擇隨機ķ從1到10）。

代碼

import random 
def distPotato(R, N, minP, maxP): 
    C = [maxP-minP for i in range(N)] 
    V = [minP for i in range(N)] 
    R-=sum(V)  
    while(R>0): 
     k = random.choice(range(10)) + 1 
     i = random.choice(range(N)) 
     k = min(k,R) 
     k = min(k, C[i]) 
     C[i]-=k 
     R-=k 
     V[i]+=k 
    return V 

distPotato(100,3,15,60) 

Answer 2

我想象在一家肉店牛肉的長度，和屠夫被要求將其切割成任意大小的N條在儘可能短的時間成爲可能。

他的第一個動作很可能是在肉隨機重擊遠，確保不切它太接近他以前的片或邊緣，直到他取得了N-1削減。

爲了您的目的，牛肉板可以改爲土豆線。

所以把這種成僞代碼：

initiate a list of chosen potatoes to empty 
while you have chosen less than N-1 potatos 
    pick a potato 
    if the potato is less than 15 potatoes away from a side 
     continue 
    if the potato is less than 15 potatoes away from a chosen potato 
     continue 
    add this potato to the chosen list 
sort the chosen list 
split the line of potatoes using the chosen potatoes as delimeters 

Answer 3

我建議只是隨機填充水桶土豆在15和60之間，直到你有小於15種的土豆離開了。然後拿出你裝滿的最後一桶，嘗試把剩下的土豆放進那個桶裏。如果它小於60，太棒了！如果它超過60，將桶分成兩半。

因此，讓我們說你這樣做了幾次，你最終得到74土豆。你現在用一個隨機數字填滿一個土豆桶。現在說它是60.你現在剩下14個土豆，對於另外一個水桶來說太少了，但是太多而不能放入你最後一個水桶。簡單來說，倒出前一個桶（再次是74個土豆），然後製作兩個桶，每個桶37個。

問題是你的最後兩個桶不會隨機（或者至少不是隨機的，如果你願意的話）和其他桶一樣，但是因爲桶裏不能少於14個土豆，你無能爲力。

Answer 4

首先，請注意您可以簡化您的問題。 「我需要0到45之間的n個數字（60 - 15），而不是」每個桶需要包含15到60個馬鈴薯，桶中的總數應該是100「 nx 15「。換句話說，用15個土豆填滿你所有的桶，現在你正在試圖決定如何使用剩餘的土豆來填充你的桶中剩餘的空間。

假設您有n個桶來填充，剩下p土豆。生成0到45之間的隨機數字r，現在剩下的是p - r土豆。你現在可以填補剩下的（n-1）桶嗎？

• 如果（P - R）< 0，你顯然不能填補剩餘的水桶，因爲你分配比你有什麼更多的，
• 如果（P - R）> 45 *（N - 1）這是不可行的：你剩下的土豆太多了，而且必須超過你的水桶容量。
• 否則，您知道如果您將r土豆放入當前存儲桶中，您仍然可以找到下一個存儲桶的解決方案。

您可以將其寫爲遞歸解決方案：對於每個連續的桶，生成一個隨機數的土豆，直到該數字不會阻止您在下一步找到解決方案。

下面是一個非常粗略的F＃實現，顯然可以對其進行改進/優化，但是說明了算法的要點。分配是包含已分配給桶的數量的int列表，其中qty是要分配的土豆數量，桶是剩餘桶的數量，min，max是桶的容量。例如用100個土豆和3桶，你會打電話解決100 3 15 60

產生的分配應該是「隨機，因爲它得到」，即它應該以相同的概率產生任何可能的分配，有一點需要注意：我認爲這些桶的順序無關緊要。鑑於該算法根據迄今分配的內容分配剩餘的土豆，根據路徑，列表的「頭」受到限制，並且分配可能會在第一個桶上分配更多。如果你想要有一個「真正的」隨機分配，一旦分配完成，你需要洗桶。

希望這會有所幫助！

let rng = new System.Random() 

let rec allocate allocation qty buckets min max = 
     match buckets with 
     | 0 -> allocation 
     | 1 -> qty :: allocation 
     | _ -> 
     let candidate = rng.Next(min, max + 1) // try a number in [min,max] 
     let rest = qty - candidate 
     if rest < (buckets - 1) * min // not enough left 
     then allocate allocation qty buckets min max // try again 
     else if rest > (buckets - 1) * max // too much left 
     then allocate allocation qty buckets min max // try again 
     else allocate (candidate :: allocation) rest (buckets - 1) min max 

let solve qty buckets min max = 
    if min * buckets > qty then failwith "unfeasible" 
    if max * buckets < qty then failwith "unfeasible" 
    allocate [] qty buckets min max