r - 如何并行化comb()？

Question

函数combn() 生成一次取m 个x 元素的所有组合。对于 nCm 小(其中 n 是 x 的元素数量)来说，它非常快速且高效，但它很快就会耗尽内存。例如:

> combn(c(1:50), 12, simplify = TRUE)
Error in matrix(r, nrow = len.r, ncol = count) : 
invalid 'ncol' value (too large or NA)

我想知道是否可以修改函数combn()，使其仅生成k个选定的组合。我们将这个新函数称为 selectedcombn()。那么我们就会:

> combn(c("a", "b", "c", "d"), m=2)
     [,1] [,2] [,3] [,4] [,5] [,6]
 [1,] "a"  "a"  "a"  "b"  "b"  "c" 
 [2,] "b"  "c"  "d"  "c"  "d"  "d" 

>chosencombn(c("a", "b", "c", "d"), m=2, i=c(1,4,6))
     [,1] [,2] [,3]
 [1,] "a"  "b"  "c" 
 [2,] "b"  "c"  "d"

>chosencombn(c("a", "b", "c", "d"), m=2, i=c(4,5))
     [,1] [,2]
 [1,] "b"  "b" 
 [2,] "c"  "d" 

我知道这样的函数需要使用组合的排序，以便人们可以立即找到给定组合的位置。这样的排序存在吗？是否可以对其进行编码以获得与combn()一样高效的函数？

Answer 1

为了了解 combn 如何排序其输出，让我们看看 combn(1:5, 3) 的输出:

combn(1:5, 3)
#      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
# [1,]    1    1    1    1    1    1    2    2    2     3
# [2,]    2    2    2    3    3    4    3    3    4     4
# [3,]    3    4    5    4    5    5    4    5    5     5

这里有很多结构。首先，所有列都是按照向下排序的，并且第一行是非递减的。以 1 开头的列下面有 combn(2:5, 2)；以 2 开头的列下面有 combn(3:5, 2)；等等。

现在让我们考虑如何构造第 8 列。我将采取的重建方法是确定该列的第一个元素(由于上面的关系，有 choose(4, 2)=6 以 1 开头的列、choose(3, 2)=3 以 2 开头的列以及 choose(2, 2)=1 以 3 开头的列) 。在我们的例子中，我们确定以 2 开头，因为第 7-9 列必须以 2 开头。

为了确定该列的第二个和后续元素，我们使用较少数量的元素重复该过程(因为 2 是我们的第一个元素，我们现在从元素 3-5 中进行选择)、一个新位置(我们'重新选择以 2) 开头的列号 8-6=2，以及要选择的新数量的剩余元素(我们还需要 3-1=2 个元素)。

下面的

getcombn 是一个迭代公式，它的作用就是:

getcombn <- function(x, m, pos) {
  combo <- rep(NA, m)
  start <- 1
  for (i in seq_len(m-1)) {
    end.pos <- cumsum(choose((length(x)-start):(m-i), m-i))
    selection <- which.max(end.pos >= pos)
    start <- start + selection
    combo[i] <- x[start - 1]
    pos <- pos - c(0, end.pos)[selection]
  }
  combo[m] <- x[start + pos - 1]
  combo
}

chosencombn <- function(x, m, all.pos) {
  sapply(all.pos, function(pos) getcombn(x, m, pos))
}
chosencombn(c("a", "b", "c", "d"), 2, c(1,4,6))
#     [,1] [,2] [,3]
# [1,] "a"  "b"  "c" 
# [2,] "b"  "c"  "d" 
chosencombn(c("a", "b", "c", "d"), 2, c(4,5))
#     [,1] [,2]
# [1,] "b"  "b" 
# [2,] "c"  "d" 

这使您能够在无法枚举所有组合的情况下计算特定列(您将耗尽内存)。例如，有 50 个选项，选择 25 个元素的方法数是 14 位数字，因此枚举所有组合可能不是一个选项。尽管如此，您仍然可以计算特定的指示组合:

chosencombn(1:50, 25, c(1, 1000000L, 1e14))
#       [,1] [,2] [,3]
#  [1,]    1    1    3
#  [2,]    2    2    4
#  [3,]    3    3    6
#  [4,]    4    4    7
#  [5,]    5    5    8
#  [6,]    6    6   11
#  [7,]    7    7   14
#  [8,]    8    8   15
#  [9,]    9    9   17
# [10,]   10   10   20
# [11,]   11   11   22
# [12,]   12   12   25
# [13,]   13   13   27
# [14,]   14   14   30
# [15,]   15   15   31
# [16,]   16   16   32
# [17,]   17   17   33
# [18,]   18   18   36
# [19,]   19   20   37
# [20,]   20   23   39
# [21,]   21   27   40
# [22,]   22   39   42
# [23,]   23   42   47
# [24,]   24   45   48
# [25,]   25   49   50