R комбинации разделены N на sub n

Question

Я за алгоритмом, который рассчитает все возможные размеры выборки бункера из общих размеров выборки. Поэтому я хочу, чтобы вычислить все комбинации 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