Rの組み合わせはNをサブNに分割します

Question

全体のサンプルサイズからすべての可能なビンサンプルサイズを計算するアルゴリズムの後です。だから私は合計（n_i）という制約にn_iのすべての組み合わせを計算したい= Nとn_i> = 1

例えばN = 10と私はいくつかの可能な組み合わせが

可能性が4つのビンのサンプルを持っています2,3,2,3別 1,1,1,7など

理想的機能は、2つのパラメータ

bins = 4 
N = 10 

を取り、すべての組み合わせを返し、感謝します

Answer 1

この問題は本質的に再帰的であり、同じパラメータ値を持つ再帰関数が複数回呼び出されるため、メモ処理で動的プログラミングを使用することで最も解決できる可能性があります。

のは、すべてのk-tuples(x1,x2,...,xk) S。T.のセットを表現するために機能partition(n,k)を定義してみましょうx1+x2+...+xk=nをそれぞれxi >= 1（パーティションn〜k空ではないサブセット、換言すれば）とする。次の図は、トップダウンの再帰を使用すると、あまりにも多くの冗長な計算が発生します方法を示しています。

私たちが見ることができるように、partition(n,k)は全てi=1,2,...n-1ためpartition(n-i,k-1) + [i]からの結果を組み合わせることによって計算することができます。関数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