隨機分手陣列分成至少3塊與均勻分佈

的大小至少爲3。舉例來說，米塊

[1,2,3,4,5,6,7,8,9,10]

和M = 3，我們可以打破它分成

a=[1,2,3,4][5,6,7][8,9,10] 
b=[1,2,3][4,5,6,7][8,9,10] 
c=[1,2,3][4,5,6][7,8,9,10]

我們可以認爲這些解決方案通過對（4,3,3）（3,4,3）派代表出席（3,3,4）。我想給一個數組n，m的函數返回一個隨機解，並返回一個均勻分佈的解（這樣你就不太可能得到一個特定的解決方案）。（這個函數需要工作n = 50，所以出於性能原因，我們不能通過計算所有可能的解決方案來做到這一點。）

因此，在上述情況下，此方法會返回[4,3,3]三分之一的時間，[3,4,3]三分之一的時間，[3,3,4]三分之一的時間。

來源

2014-12-23 GoatsRule

你有什麼試過的？你需要表現出一些努力，然後我們可以幫助你解決你無法弄清的任何錯誤。 – forgivenson

我沒有得到你給的東西，你回來的東西 – CMPS

上述情況下的返回值是[4,3,3]，[3,4,3]和[3,3,4] 。（它總是會返回總和爲n的m個整數列表）。 – GoatsRule

只是一個想法：

假設M = 3，N = 20。我們所能做的就是要做到這一點：

選擇m和n之間的數 -
（3至14之間），2 * M比方說，我們隨機6.這將是第一套，讓我們通話it p1
選擇我們[m，[n - m - p1]]的新子集即[3，20 - 6 - 3]或[3，11]的子集之間的數字假設我們滾動10.這是p2
餘數（或p3）的大小將爲20 -p1 -p2 = 4

最終設置將是[6，10，4]

這項工作？它不需要對原始列表進行任何形式的迭代。你唯一的迭代將超過m而不依賴於n。

我可以嘗試使這個更通用的變量m（步驟1將需要稍微改變，步驟3和5將在一個循環），但我相信你可以解決這個解決方案是可以接受的您。例改寫爲第1步是：

Choose a number between m and n - [m - 1] * m

來源

2014-12-23 20:56:52 kha

將這項工作？

def randomCollate(item, chunk) { 
    def collated = item.collate(chunk) 
    def remainder = collated.reverse().takeWhile { it.size() != chunk }.flatten() 
    def randomIdx = new Random().nextInt((collated - remainder).size()) 
    collated[randomIdx] += remainder 
    collated - [ remainder ] 
} 

randomCollate(1..50, 3)

來源

2014-12-24 00:57:29 dmahapatro

另一個想法我只是

計算你有多少陣列將有大小米，多少大小爲M + 1（或不同SICE）。我們稱這些值爲x和y。
計算可能的置換量[3,3,4]，[3,4,3]，[4,3,3] - > 3置換（x + y）Py（二項式係數）
選擇從0開始的隨機置換 - 可能的置換。讓我們打電話給Z.
從現在開始，我不完全知道如何做到這一點，但我會試試這個：
想象一下，你得到一個二進制數字，其中有n位數字，其中y是零。獲得Zst可能的二進制數，其中包含y個零和x個。
實例二進制：100101101
你的結果將是[X，Y，Y，X，Y，X，X，Y，X]

我希望你明白我的意思。

來源

2014-12-24 01:36:19 Joba

爲每個步驟允許隨機範圍n-m*min（min在您的示例中爲3）;然後從該範圍中選擇一個數字，加上min，作爲r。如果m是2返回的列表r和n-r。否則返回r以及與n-r, m-1的遞歸調用的結果。洗牌這個，你有隨機大小的塊。

rnd = new Random() 

// build the chunk size list to randomly split `n` elements in `m` parts, 
// where each part is at least of size `min` 
// needs a shuffle afterwards 
def s(n,m,min=3) { 
    def l = n-m*min // the range where we can pick a random offset 
    def r = min + (l?rnd.nextInt(l):0) // result for this step with optional random part 
    m==2 ? [r,n-r] : [r]+s(n-r,m-1) // only two remaining? pick result and remainder, or recurse 
} 

def tests = [[9,3,3],[10,3,3],[27,9,3],[4,2,2]] 
1000.times{ 
    tests.each{ n,m,min -> 
     def r = s(n,m,min) 
     assert r.sum()==n 
     assert r.size()==m 
     assert r.every{ it>= min } 
    } 
} 

def items = (0..9).collect() // test list 
def slices = s(items.size(),3) // get the chunk sizes 
Collections.shuffle(slices) // shuffle the result 
// create ranges and use them to get the slices; should be another one or two methods 
println slices.inject([sum:0,result:[]]) { r,s -> r.result<<items[((r.sum)..(r.sum+s-1))]; r.sum+=s; r }.result 
//=> e.g. [[0, 1, 2, 3], [4, 5, 6], [7, 8, 9]]

來源

2014-12-24 14:48:19 cfrick

隨機分手陣列分成至少3塊與均勻分佈

回答

相關問題