r - 在 R 中存储所有可能的排列

Question

我在“gtools”下使用排列命令。但是，它产生了内存问题。

我尝试了以下方法:

library(gtools)
permutations(n=15,r=8)

但是，我收到以下错误消息:

 Error in next_permutations(n, k, -1L, NULL, x, freq, replace, type) : 
cannot allocate vector of length 2075673600.

这是我正在做的非常基础的事情。我需要的排列远不止 n=15 和 k=8。

Answer 1

我之前的回答有两个缺点:

• 它只计算 1:r 的排列。
• 排列数错误，因为我使用了 n!/r! 而不是 n!/(n - r)!.

最后一点将 n = 15 和 r = 8 的结果矩阵的大小增加了 8 倍，达到大约 8 GB。这突出了 Ben Bolker 在评论中提出的观点:应该考虑以迭代方式处理排列。

无论如何，生成所有排列的一个简单方法是先用combn() 生成所有组合。之后，可以使用 C++ 中的 std::next_permutation 为每个组合生成排列:

src1 <- '
IntegerMatrix permute_combinations(const IntegerMatrix& combs) {
  size_t numComb(combs.cols());
  size_t r(combs.rows());
  size_t numPermPerComb(1);
  for(size_t i = 1; i <= r; ++i) numPermPerComb *= i;
  size_t numPerm = numComb * numPermPerComb;
  IntegerMatrix perms(numPerm, r);

  for(size_t i = 0; i < numComb; ++i) {
    IntegerVector v = combs(_, i);
    for (size_t j = 0; j < numPermPerComb; ++j) {
      perms(i * numPermPerComb + j, _) = v;
      std::next_permutation(v.begin(), v.end());
    }
  }
  return perms;
}
'

Rcpp::cppFunction(src1)
system.time(perms <- permute_combinations(combn(15, 8)))
#>        User      System verstrichen 
#>      54.572       1.136      56.006
dim(perms)
#> [1] 259459200         8
object.size(perms)
#> 8302694600 bytes
head(perms)
#>      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
#> [1,]    1    2    3    4    5    6    7    8
#> [2,]    1    2    3    4    5    6    8    7
#> [3,]    1    2    3    4    5    7    6    8
#> [4,]    1    2    3    4    5    7    8    6
#> [5,]    1    2    3    4    5    8    6    7
#> [6,]    1    2    3    4    5    8    7    6
tail(perms)
#>              [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
#> [259459195,]   15   14   13   12   11    8    9   10
#> [259459196,]   15   14   13   12   11    8   10    9
#> [259459197,]   15   14   13   12   11    9    8   10
#> [259459198,]   15   14   13   12   11    9   10    8
#> [259459199,]   15   14   13   12   11   10    8    9
#> [259459200,]   15   14   13   12   11   10    9    8

原版

生成的矩阵略低于 1 GB，因此 gtools 代码中肯定存在一些低效问题。这里有一个与 Rcpp 一起使用的快速而肮脏的 C++ 版本:

src <- 'IntegerMatrix permutations(int n, int r) {
  size_t numPerm(1);
  for(int i = n; i > r; --i) {
    numPerm *= i;
  }
  IntegerMatrix result(numPerm, r);

  IntegerVector v(r);
  std::iota (std::begin(v), std::end(v), 1);

  for (size_t i = 0; i < numPerm; ++i) {
    result(i, _) = v;
    std::next_permutation(v.begin(), v.end());
  }
  return result;
}'
Rcpp::cppFunction(src)
system.time(perms <- permutations(15, 8))
#>        User      System verstrichen 
#>       6.909       0.060       6.970
dim(perms)
#> [1] 32432400        8
object.size(perms)
#> 1037837000 bytes
head(perms)
#>      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
#> [1,]    1    2    3    4    5    6    7    8
#> [2,]    1    2    3    4    5    6    8    7
#> [3,]    1    2    3    4    5    7    6    8
#> [4,]    1    2    3    4    5    7    8    6
#> [5,]    1    2    3    4    5    8    6    7
#> [6,]    1    2    3    4    5    8    7    6