如何在 Rcpp 中的 n 之间创建 k 个元素的组合？

Question

下午好，

我们知道在 R 中，我们可以通过这种方式检索 A = { 1 , 2 , ... , n } 之间的 k 个元素的所有可能组合：

示例： A = { 1 , 2, ,3 ,4 ,5 } 和 K = 3

> C_wo <- combn(1:5, 3)
> C_wo
     [,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

我的问题：

是否有用于在 rcpp 中创建这些组合的内置函数？

提前致谢！

Answer 1

我不认为有这样的内置 Rcpp 函数，但这些函数在 {RcppAlgos} 中实现。

Answer 2

试试这个。

library(microbenchmark)

z1 <- combncpp(50,5)
z2 <- combn(50,5)
identical(t(z1), z2) # I prefer column-wise so it is transposed
[1] TRUE

microbenchmark(cpp = combncpp(25,10),
               r = combn(25,10), times = 5)

Unit: milliseconds
expr min      lq        mean      median    uq        max       neval
cpp  275.882  295.9357  295.4369  299.9468  300.0149  305.4051  5
r    2729.003 2755.1360 2789.3226 2798.6658 2819.9010 2843.9075 5

函数：

#include <Rcpp.h>
#include <algorithm>
using namespace Rcpp;

// [[Rcpp::export]]
uint64_t choosecpp(uint64_t n, uint64_t k) {
  if(k == 0) return 1;
  return (n * choosecpp(n - 1, k - 1)) / k;
}

// [[Rcpp::export]]
IntegerMatrix combncpp(int N, int K) {
  if(K > N) Rcpp::stop("K > N");
  std::string bitmask(K, 1);
  bitmask.resize(N, 0);

  uint64_t n_combos = choosecpp(N,K);
  IntegerMatrix results(n_combos, K);
  uint64_t row_position = 0;
  do {
    uint64_t col_position = 0;
    for (int i = 0; i < N; ++i)  {
      if (bitmask[i]) {
        results(row_position, col_position) = i+1;
        col_position++;
      }
    }
    row_position++;
  } while (std::prev_permutation(bitmask.begin(), bitmask.end()));
  return results;
}

归功于此，该函数是根据此处列出的算法修改的：Creating all possible k combinations of n items in C++

如何在 Rcpp 中的 n 之间创建 k 个元素的组合？

How to create a combination of k elements between n in Rcpp?

r

rcpp