组合数学的部分和

Question

组合数学的部分和

4

我在R中寻找一个名为partial.sum()的函数，它接受一个数字向量并返回所有部分和按升序排序后的向量：

test=c(2,5,10)
partial.sum(test)

# 2 5 7 10 12 15 17
## 2 is the sum of element 2
## 5 is the sum of element 5    
## 7 is the sum of elements 2 & 5    
## 10 is the sum of element 10    
## 12 is the sum of elements 2 & 10    
## 15 is the sum of elements 5 & 10
## 17 is the sum of elements 2 & 5 & 10

- user2030503

1

你尝试过吗？ - rawr

我觉得你错过了12。而且我猜你忽略了不包括任何元素（0）的部分和。 - Dason

谢谢，我忘记了12。我已经相应地修改了问题。不需要0元素的解决方案。 - user2030503

3个回答

3

这种方法可能不太适用于大规模应用，并且没有考虑输入向量中可能存在重复项或者答案中可能存在重复项的情况。如果您关心这些问题，可以稍后使用unique。

partial.sum <- function(x){
  n <- length(x)
  # Something that will help get us every possible subset
  # of the original vector
  out <- do.call(expand.grid, replicate(n, c(T,F), simplify = F))
  # Don't include the case where we don't grab any elements
  out <- head(out, -1)

  # ans <- apply(out, 1, function(row){sum(x[row])})
  # As flodel points out the following will be faster than
  # the previous line
  ans <- data.matrix(out) %*% x
  # If you want only unique value then add a call to unique here
  ans <- sort(unname(ans))
  ans
}

- Dason

2

我本来也在写同样的答案。不过我认为矩阵乘法会更快：ans <- sort(unique(data.matrix(out) %*% x)) - flodel

2

以下是使用combn生成组合求和的迭代方法。适用于长度大于1的向量。

partial.sum <- function(x) {
  sort(unique(unlist(sapply(seq_along(x), function(i) colSums(combn(x,i))))))
}
## [1]  2  5  7 10 12 15 17

处理长度小于2的情况，需要测试其长度：

partial.sum <- function(x) {
  if (length(x) > 1) {
    sort(unique(unlist(sapply(seq_along(x), function(i) colSums(combn(x,i))))))
  } else {
    x
  }
}

一些时间方面的数据，使用rbenchmark得到，与flodel的结果并不完全相同。我修改了Dason的代码，去除了注释，并添加了一个对unique的调用。我的代码版本是第一个，没有if语句。在这里，flodel的代码明显更好。

> test <- 1:10
> benchmark(matthew(test), flodel(test), dason(test), replications=100)
           test replications elapsed relative user.self sys.self user.child sys.child
3   dason(test)          100   0.180   12.857     0.175    0.004          0         0
2  flodel(test)          100   0.014    1.000     0.015    0.000          0         0
1 matthew(test)          100   0.244   17.429     0.242    0.001          0         0

> test <- 1:20
> benchmark(matthew(test), flodel(test), dason(test), replications=1)
           test replications elapsed relative user.self sys.self user.child sys.child
3   dason(test)            1   5.231   98.698     5.158    0.058          0         0
2  flodel(test)            1   0.053    1.000     0.053    0.000          0         0
1 matthew(test)            1   2.184   41.208     2.180    0.000          0         0

> test <- 1:25
> benchmark(matthew(test), flodel(test), dason(test), replications=1)
           test replications elapsed relative user.self sys.self user.child sys.child
3   dason(test)            1 288.957  163.345   264.068   23.859          0         0
2  flodel(test)            1   1.769    1.000     1.727    0.038          0         0
1 matthew(test)            1  75.712   42.799    74.745    0.847          0         0

- Matthew Lundberg

你需要处理 length(x) == 1 的情况，责备 combn。 - flodel

它比Dason的快20个元素（去掉注释，并在两者中都添加“unique”）。 - Matthew Lundberg

1

如果您的机器上矩阵乘法速度较慢，请考虑更改您的 BLAS 库。如果您有兴趣且从未探究过，可以去看看。 - flodel

1

@Arun 我添加了一个调用unique来删除重复项。如果删除unique，你会得到两个3。 - Matthew Lundberg

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- flodel · Accepted Answer

这里是一种使用递归的方法。(不保证它是高效的)

partial.sum <- function(x) {
   slave <- function(x) {
      if (length(x)) {
         y <- Recall(x[-1])
         c(y + 0, y + x[1])
      } else 0
   }
   sort(unique(slave(x)[-1]))
}

partial.sum(c(2,5,10))
# [1]  2  5  7 10 12 15 17

编辑：好吧，事实证明它比我想象的要快一些：

x <- 1:20
microbenchmark(flodel(x), dason(x), matthew(x), times = 10)
# Unit: milliseconds
#        expr        min        lq     median        uq       max neval
#   flodel(x)   86.31128   86.9966   94.12023  125.1013  163.5824    10
#    dason(x) 2407.27062 2461.2022 2633.73003 2846.2639 3031.7250    10
#  matthew(x) 3084.59227 3191.7810 3304.36064 3693.8595 3883.2767    10

（我在达森和马修的函数中适当添加了sort和/或unique，以进行公平比较。）