如何找到所有可能的k整數，其總和等於一定數量在R

Question

假設我有一個整數n和k，我需要找到k整數的所有可能的組合，總和爲n。我想知道如何有效地實現這一點。

現在，我正在做的是超級慢，我創建了kth從1到n的序列笛卡爾乘積。然後遍歷所有可能的組合以檢查它是否滿足總和。下面是我的代碼。

第一得到ķ笛卡爾乘積

cart = function(v,k){ 
    x = v 
    f = v 
    for(i in 1:(k-1)){ 
    f = merge(f,x,all=T) 
    f = as.matrix(f) 
    colnames(f) = NULL 
    } 
    return(f) 
} 

v是從1到n和k的序列是整數

然後遍歷

combine = cart(v=seq(1,n),k=k) 
sum = 0 
for(i in 1:dim(combine)[1]){ 
    if(sum(combine[i,])==n){ 
    sum = sum + sum(combine[i,]) 
    } 
} 

這是超慢和我想知道有沒有更快的方法來實現這一點？

Answer 1

編輯基於澄清問題的意見：

聽起來像是你想要的所有成分，而不是整數n的所有分區。 （僅在其字詞的順序不同的兩個序列都被認爲是相同的分區，但不同組合物。）

要獲得的組合物，使用compositions()函數從分區包：

library(partitions) 
compositions(4, 3, include.zero=FALSE) 
#   
# [1,] 2 1 1 
# [2,] 1 2 1 
# [3,] 1 1 2 

---

原來的答覆，留在原地，直到包筆者有機會看到它：

如果我正確理解你的問題，你可以使用分區的restrictedparts()包包。

例如：

library(partitions) 

restrictedparts(9,4) 
#           
# [1,] 9 8 7 6 5 7 6 5 4 5 4 3 6 5 4 4 3 3 
# [2,] 0 1 2 3 4 1 2 3 4 2 3 3 1 2 3 2 3 2 
# [3,] 0 0 0 0 0 1 1 1 1 2 2 3 1 1 1 2 2 2 
# [4,] 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 2 

## Or, for partitions employing only non-zero integers 
restrictedparts(9,4,include.zero=FALSE) 
#     
# [1,] 6 5 4 4 3 3 
# [2,] 1 2 3 2 3 2 
# [3,] 1 1 1 2 2 2 
# [4,] 1 1 1 1 1 2 

由於在第二次的restrictedparts最後一行一個小錯誤，它可以在給定的限制，允許只有一個分區拋出一個錯誤。我已經發出了建議修復至包的作者，但在此期間，你可以通過設置函數參數decreasing=FALSE解決這個問題：

## Throws an error 
restrictedparts(4,3,include.zero=FALSE) 
# Error in class(x) <- "matrix" : 
# invalid to set the class to matrix unless the dimension attribute is of # length 2 (was 0) 

## Works just fine 
restrictedparts(4,3,include.zero=FALSE,decreasing=FALSE) 
#  
# [1,] 1 
# [2,] 1 
# [3,] 2 

Answer 2

下面是使用combn一個基礎R方法。比方說你有整數1到12，你想找到所有的組5個號碼那筆以20

myGroups <- combn(1:12, 5) 
mysums <- combn(1:12, 5, FUN=sum, simplify=TRUE) 

myAnswers <- myGroups[, mysums == 20] 

這將返回一個矩陣，其中列是數字的組：

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

這將很容易包裝在一個函數中。在下面的函數中，x是輸入向量，我在上面的例子中設置爲1:12，k和n在OP的問題中定義。

myfunction <- function(x, k, n) { 
    myGroups <- combn(x, k) 
    mysums <- combn(x, k, FUN=sum, simplify=TRUE) 

    myGroups[, mysums == n] 
} 

注
這種方法假定在X中的每個條目將被一次在計算上的整數使用，所以0：即最多使用它們的4，myfunction返回添加到9 9：

myfunction(0:9, 4, 9) 
    [,1] [,2] [,3] 
[1,] 0 0 0 
[2,] 1 1 2 
[3,] 2 3 3 
[4,] 6 5 4 

注
如果目標是允許重複使用這些整數的，我們只是必須調整我們喂myfunction。請注意，這將導致重複輸出集合，因爲訂單對combn重要。

---

如果重複整數將參與，利用combn已被修改爲返回一個列表，所以我們可以用unique下降重複集：

myfunctionDupes <- function(x, k, n) { 
    # return list instead of matrix, with elements sorted 
    myGroups <- lapply(combn(x, k, simplify=FALSE), sort) 
    # find duplicates 
    dupes <- duplicated(myGroups) 
    # subset summations to those where myGroups is not a duplicate 
    mysums <- combn(x, k, FUN=sum, simplify=TRUE)[!dupes] 
    # subset myGroups to the unique values then those with sums == n 
    myGroups <- (myGroups[!dupes])[mysums == n] 
    # return a matrix 
    do.call(cbind, myGroups) 
} 

這需要一點時間來運行在@喬希 - 奧布萊恩的例子，但是它產生相同的結果：

myfunctionDupes(rep(0:9, 4), 4, 9) 
[,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12] [,13] [,14] [,15] [,16] [,17] [,18] 
[1,] 0 0 0 0 0 0 0 0 0  0  0  0  1  1  1  1  1  2 
[2,] 1 1 1 1 0 2 2 0 0  3  0  0  2  2  1  1  1  2 
[3,] 2 3 4 1 1 3 2 2 3  3  4  0  3  2  2  3  1  2 
[4,] 6 5 4 7 8 4 5 7 6  3  5  9  3  4  5  4  6  3