查找一组数字的所有组合，这些组合加起来等于某个总数

Question

我见过一些类似问题的解决方案，但它们都需要对要加在一起的项目数进行迭代。

我的目标是：从一个数字列表中，找到所有加起来等于某个总数的组合（无需替换）。例如，如果我有数字 1,1,2,3,5 和总数 5，它应该 return 5、2,3 和 1,1,3.

我尝试使用 combn，但它要求您指定每个组合中的项目数。有没有办法允许任意大小的解决方案集？

Answer 1

我采纳了你的 combn 想法并遍历了集合的可能大小。

func = function(x, total){
    M = length(x)
    y = NULL
    total = 15
    for (m in 1:M){
        tmp = combn(x, m)
        ind = which(colSums(tmp) == total)
        if (length(ind) > 0){
            for (j in 1:length(ind))
                y = c(y, list(tmp[,ind[j]]))
            }
        }
    return (unique(lapply(y, sort)))
    }

x = c(1,1,2,3,5,8,13)

> func(x, 15)
[[1]]
[1]  2 13

[[2]]
[1]  1  1 13

[[3]]
[1] 2 5 8

[[4]]
[1] 1 1 5 8

[[5]]
[1] 1 1 2 3 8

显然，这会随着 M 的增长而出现问题，因为 tmp 会很快变大并且 y 的长度不能（也许？）预先确定。

Answer 2

类似于mickey的回答，我们可以在另一个循环机制中使用combn。我将使用 lapply:

vec <- c(1,1,2,3,5)
ans <- 5

Filter(length, lapply(seq_len(length(vec)),
       function(i) {
         v <- combn(vec, i)
         v[, colSums(v) == ans, drop = FALSE]
       }))
# [[1]]
#      [,1]
# [1,]    5
# [[2]]
#      [,1]
# [1,]    2
# [2,]    3
# [[3]]
#      [,1]
# [1,]    1
# [2,]    1
# [3,]    3

您可以省略 Filter(length, 部分，尽管它可能 return 一些空矩阵。它们很容易处理和忽略，我只是认为移除它们在美学上是首选。

这个方法给你一个矩阵，每列有多个候选，所以

ans <- 4
Filter(length, lapply(seq_len(length(vec)),
       function(i) {
         v <- combn(vec, i)
         v[, colSums(v) == ans, drop = FALSE]
       }))
# [[1]]
#      [,1] [,2]
# [1,]    1    1
# [2,]    3    3
# [[2]]
#      [,1]
# [1,]    1
# [2,]    1
# [3,]    2

如果重复是个问题，您可以随时这样做：

Filter(length, lapply(seq_len(length(vec)),
       function(i) {
         v <- combn(vec, i)
         v <- v[, colSums(v) == ans, drop = FALSE]
         v[,!duplicated(t(v)),drop = FALSE]
       }))
# [[1]]
#      [,1]
# [1,]    1
# [2,]    3
# [[2]]
#      [,1]
# [1,]    1
# [2,]    1
# [3,]    2

Answer 3

现在这里有一个涉及 gtools 的解决方案：

# Creating lists of all permutations of the vector x
df1 <- gtools::permutations(n=length(x),r=length(x),v=1:length(x),repeats.allowed=FALSE)
ls1 <- list()
for(j in 1:nrow(df1)) ls1[[j]] <- x[df1[j,1:ncol(df1)]]  

# Taking all cumulative sums and filtering entries equaling our magic number
sumsCum <- t(vapply(1:length(ls1), function(j) cumsum(ls1[[j]]), numeric(length(x))))
indexMN <- which(sumsCum == magicNumber, arr.ind = T)
finalList <- list()
for(j in 1:nrow(indexMN)){
    magicRow <- indexMN[j,1]
    magicCol <- 1:indexMN[j,2]
    finalList[[j]] <- ls1[[magicRow]][magicCol]
}
finalList <- unique(finalList)

其中 x = c(1,1,2,3,5) 和 magicNumber = 5。这是初稿，我相信它可以在这里和那里进行改进。

Answer 4

这正是 RcppAlgos（我是作者）中的 combo/permuteGeneral 的目的。由于我们的样本向量中有特定元素的重复，我们将找到符合我们标准的 multisets 的组合。请注意，这不同于更常见的通过重复生成组合的情况，其中每个元素允许重复 m 次。对于许多组合生成函数，多重集会带来问题，因为引入了重复项并且必须加以处理。如果数据量相当大，这可能会成为代码中的瓶颈。 RcppAlgos 中的函数可以有效地处理这些情况，而不会产生任何重复的结果。我应该提一下，还有一些其他很棒的库可以很好地处理多重集：multicool 和 arrangements.

继续手头的任务，我们可以利用 comboGeneral 的约束参数来查找满足特定条件的向量的所有组合：

vec <- c(1,1,2,3,5)  ## using variables from @r2evans
uni <- unique(vec)
myRep <- rle(vec)$lengths
ans <- 5

library(RcppAlgos)
lapply(seq_along(uni), function(x) {
    comboGeneral(uni, x, freqs = myRep,
                 constraintFun = "sum",
                 comparisonFun = "==",
                 limitConstraints = ans)
})

[[1]]
[,1]
[1,]    5

[[2]]
[,1] [,2]
[1,]    2    3

[[3]]
[,1] [,2] [,3]
[1,]    1    1    3

[[4]]
[,1] [,2] [,3] [,4]  ## no solutions of length 4

这些功能经过高度优化，可以很好地扩展到更大的案例。例如，请考虑以下将产生超过 3000 万种组合的示例：

## N.B. Using R 4.0.0 with new updated RNG introduced in 3.6.0
set.seed(42)
bigVec <- sort(sample(1:30, 40, TRUE))

rle(bigVec)
Run Length Encoding
  lengths: int [1:22] 2 1 2 3 4 1 1 1 2 1 ...
  values : int [1:22] 1 2 3 4 5 7 8 9 10 11 ...

bigUni <- unique(bigVec)
bigRep <- rle(bigVec)$lengths
bigAns <- 199
len <- 12

comboCount(bigUni, len, freqs = bigRep)
[1] 32248100

所有 300000+ 个结果都很快返回：

system.time(bigTest <- comboGeneral(bigUni, len, freqs = bigRep,
                                    constraintFun = "sum",
                                    comparisonFun = "==",
                                    limitConstraints = bigAns))
 user  system elapsed 
0.273   0.004   0.271

head(bigTest)
     [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12]
[1,]    1    1    2    3    4   25   26   26   26    27    28    30
[2,]    1    1    2    3    5   24   26   26   26    27    28    30
[3,]    1    1    2    3    5   25   25   26   26    27    28    30
[4,]    1    1    2    3    7   24   24   26   26    27    28    30
[5,]    1    1    2    3    7   24   25   25   26    27    28    30
[6,]    1    1    2    3    7   24   25   26   26    26    28    30

nrow(bigTest)
[1] 280018

all(rowSums(bigTest) == bigAns)
[1] TRUE

附录

我必须提一下，一般当我看到像这样的问题时："finding all combinations that sum to a particular number" 我的第一个想法是 integer partitions. For example, in the related problem Getting all combinations which sum up to 100 in R，我们可以很容易地用 partitions 图书馆。然而，这种方法并没有扩展到一般情况（正如我们在这里遇到的那样），在这种情况下，向量包含特定的重复，或者我们有一个向量包含的值不容易转换为等价的整数（例如，向量 (0.1, 0.2, 0.3, 0.4)可以很容易地被视为 1:4，但是将 c(3.98486 7.84692 0.0038937 7.4879) 视为整数并随后应用整数分区方法将需要大量的计算能力，从而使该方法无用）。

Answer 5

目前为止不是最高效但最紧凑的：

x <- c(1,1,2,3,5)
n <- length(x)
res <- 5
unique(combn(c(x,rep(0,n-1)), n, function(x) x[x!=0][sum(x)==res], FALSE))[-1]
# [[1]]
# [1] 1 1 3
# 
# [[2]]
# [1] 2 3
# 
# [[3]]
# [1] 5
#

查找一组数字的所有组合，这些组合加起来等于某个总数

Find all combinations of a set of numbers that add up to a certain total

combinations

r

combinatorics

subset-sum

附录