R組合將N拆分爲子代碼

Question

我使用的算法將根據總體樣本大小計算所有可能的bin樣本大小。因此，我希望與約束是總和（n_i個）來計算n_i個的所有組合= N和n_i個> = 1

例如N = 10和我有4個樣品倉一些可能的組合可以是

2,3,2,3另一 1,1,1,7等

理想的功能將需要兩個參數

bins = 4 
N = 10 

，並返回所有組合，感謝

Answer 1

該問題本質上是遞歸的，可以通過使用memoization進行動態編程來最好地解決（因爲具有相同參數值的遞歸函數將被多次調用，記住已經計算的值是有意義的）。

讓我們定義功能partition(n,k)來表示所有的設置k-tuples(x1,x2,...,xk) s.t. x1+x2+...+xk=n，其中每個xi >= 1（分區n分成k非空子集，換句話說）。下圖顯示瞭如何採用自頂向下的遞歸會遇到太多的冗餘計算：

正如我們所看到的，partition(n,k)可以通過從結果結合partition(n-i,k-1) + [i]所有i=1,2,...n-1來計算。讓我們將partition(n,k)函數的值存儲在表中，作爲D[n,k]（實現爲list of lists）。

partition <- function(n, k, lst) { 

    DT <- rep(list(list()),n*k) # the dynamic programming table as list of lists 
    for (i in 1:n) { 
    DT[[i]][[1]] <- list(i) 
    } 

    for (i in 2:n) { 
    for (j in 2:k) { 
     temp <- list() 
     for (m in 1:(i-1)) { 
     if (i-m >= j-1) { 
      temp <- c(temp, lapply(DT[[i-m]][[j-1]], function(x) c(x,m))) 
     } 
     } 
     DT[[i]][[j]] <- temp 
    } 
    } 

    return(DT[[n]][[k]]) 

}  

partition(10,4,list()) 

# output 
[[1]] 
[1] 7 1 1 1 

[[2]] 
[1] 6 2 1 1 

[[3]] 
[1] 5 3 1 1 

[[4]] 
[1] 4 4 1 1 

[[5]] 
[1] 3 5 1 1 

[[6]] 
[1] 2 6 1 1 

[[7]] 
[1] 1 7 1 1 

[[8]] 
[1] 6 1 2 1 

[[9]] 
[1] 5 2 2 1 

[[10]] 
[1] 4 3 2 1 

[[11]] 
[1] 3 4 2 1 

[[12]] 
[1] 2 5 2 1 

[[13]] 
[1] 1 6 2 1 

[[14]] 
[1] 5 1 3 1 

[[15]] 
[1] 4 2 3 1 

[[16]] 
[1] 3 3 3 1 

[[17]] 
[1] 2 4 3 1 

[[18]] 
[1] 1 5 3 1 

[[19]] 
[1] 4 1 4 1 

[[20]] 
[1] 3 2 4 1 

[[21]] 
[1] 2 3 4 1 

[[22]] 
[1] 1 4 4 1 

[[23]] 
[1] 3 1 5 1 

[[24]] 
[1] 2 2 5 1 

[[25]] 
[1] 1 3 5 1 

[[26]] 
[1] 2 1 6 1 

[[27]] 
[1] 1 2 6 1 

[[28]] 
[1] 1 1 7 1 

[[29]] 
[1] 6 1 1 2 

[[30]] 
[1] 5 2 1 2 

[[31]] 
[1] 4 3 1 2 

[[32]] 
[1] 3 4 1 2 

[[33]] 
[1] 2 5 1 2 

[[34]] 
[1] 1 6 1 2 

[[35]] 
[1] 5 1 2 2 

[[36]] 
[1] 4 2 2 2 

[[37]] 
[1] 3 3 2 2 

[[38]] 
[1] 2 4 2 2 

[[39]] 
[1] 1 5 2 2 

[[40]] 
[1] 4 1 3 2 

[[41]] 
[1] 3 2 3 2 

[[42]] 
[1] 2 3 3 2 

[[43]] 
[1] 1 4 3 2 

[[44]] 
[1] 3 1 4 2 

[[45]] 
[1] 2 2 4 2 

[[46]] 
[1] 1 3 4 2 

[[47]] 
[1] 2 1 5 2 

[[48]] 
[1] 1 2 5 2 

[[49]] 
[1] 1 1 6 2 

[[50]] 
[1] 5 1 1 3 

[[51]] 
[1] 4 2 1 3 

[[52]] 
[1] 3 3 1 3 

[[53]] 
[1] 2 4 1 3 

[[54]] 
[1] 1 5 1 3 

[[55]] 
[1] 4 1 2 3 

[[56]] 
[1] 3 2 2 3 

[[57]] 
[1] 2 3 2 3 

[[58]] 
[1] 1 4 2 3 

[[59]] 
[1] 3 1 3 3 

[[60]] 
[1] 2 2 3 3 

[[61]] 
[1] 1 3 3 3 

[[62]] 
[1] 2 1 4 3 

[[63]] 
[1] 1 2 4 3 

[[64]] 
[1] 1 1 5 3 

[[65]] 
[1] 4 1 1 4 

[[66]] 
[1] 3 2 1 4 

[[67]] 
[1] 2 3 1 4 

[[68]] 
[1] 1 4 1 4 

[[69]] 
[1] 3 1 2 4 

[[70]] 
[1] 2 2 2 4 

[[71]] 
[1] 1 3 2 4 

[[72]] 
[1] 2 1 3 4 

[[73]] 
[1] 1 2 3 4 

[[74]] 
[1] 1 1 4 4 

[[75]] 
[1] 3 1 1 5 

[[76]] 
[1] 2 2 1 5 

[[77]] 
[1] 1 3 1 5 

[[78]] 
[1] 2 1 2 5 

[[79]] 
[1] 1 2 2 5 

[[80]] 
[1] 1 1 3 5 

[[81]] 
[1] 2 1 1 6 

[[82]] 
[1] 1 2 1 6 

[[83]] 
[1] 1 1 2 6 

[[84]] 
[1] 1 1 1 7 

如果我們想唯一的分區，丟棄的話，我們可以梳理每個列表，然後採取獨特的，如下所示。

unique(lapply(partition(10,4,list()), function(x)sort(x))) 
[[1]] 
[1] 1 1 1 7 

[[2]] 
[1] 1 1 2 6 

[[3]] 
[1] 1 1 3 5 

[[4]] 
[1] 1 1 4 4 

[[5]] 
[1] 1 2 2 5 

[[6]] 
[1] 1 2 3 4 

[[7]] 
[1] 1 3 3 3 

[[8]] 
[1] 2 2 2 4 

[[9]] 
[1] 2 2 3 3