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

Question

Good afternoon ,

We know that in R , we can retrieve all possible combinations of k elements between A = { 1 , 2 , ... , n } in that manner :

Example : A = { 1 , 2, ,3 ,4 ,5 } and 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

My question :

Is there any built-in function for Creating those combinations in rcpp ?

Thank You in advance !

score 5 · Accepted Answer · answered Feb 20 '20 at 16:42

5

I don't think there are such built-in Rcpp functions but these kinds of functions are implemented in {RcppAlgos}.

answered Feb 20 '20 at 16:42

F. Privé

11,423
2
27
78

, i think this is an R package . I can't use those algos in rcpp ? – Tou Mou Feb 20 '20 at 16:44
F. Privé , how can i use this package in rcpp , not in R ? – Tou Mou Feb 20 '20 at 16:52
2

I mean, just look at the code in `src/`, everything is implemented in Rcpp. – F. Privé Feb 20 '20 at 17:58

thc · Answer 2 · 2020-02-21T00:28:57.540

Try this out.

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

The function:

#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;
}

Credit where it is due, the function was modified from the algorithm listed here: Creating all possible k combinations of n items in C++

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

2 Answers2