Как создать комбинацию из k элементов между n в R cpp? - PullRequest
Новая
       6

Как создать комбинацию из k элементов между n в R cpp?

0 голосов
/ 20 февраля 2020

Добрый день,

Мы знаем, что в R мы можем извлечь все возможные комбинации k элементов между A = {1, 2, ..., n} таким образом:

Пример: 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

Мой вопрос:

Есть ли встроенная функция для создания этих комбинаций в r cpp?

Заранее спасибо!

Ответы [ 2 ]

5 голосов
/ 20 февраля 2020

Я не думаю, что есть такие встроенные функции R cpp, но эти виды функций реализованы в {RcppAlgos} .

1 голос
/ 21 февраля 2020

Попробуйте это. 

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

Кредит, где это необходимо, функция была изменена из алгоритма, перечисленного здесь: Создание всех возможных k комбинаций из n элементов в C ++

...