r - Rcpp Power Set implementation : attempt to set index 8/8 in SET_VECTOR_ELT -

consider function takes set of elements input vector , returns power set in list:

> pwr_set(letters[1:3])  [[1]] character(0)  [[2]] [1] "a"  [[3]] [1] "b"  [[4]] [1] "a" "b"  [[5]] [1] "c"  [[6]] [1] "a" "c"  [[7]] [1] "b" "c"  [[8]] [1] "a" "b" "c" 

r definition:

pwr_set <- function(els){   n_els <- length(els)   out <- vector(mode="list",length = 2 ^ n_els)   out[[1]] <- character()     # first element in power set empty set    listidx <- 1l       # start listidx    for(i in 1l:n_els){     for(j in 1l:listidx){       listidx <- listidx + 1l       out[[listidx]] <- c(out[[j]], els[i])     }   }   out } 

i have come following translation implement in rcpp:

#include <rcpp.h> #include <math.h> using namespace rcpp;   // [[rcpp::export]] list pwr_set_cpp(charactervector els) {    int n_els = els.size();         // size of set   int pwrset_card = pow(2,n_els); // number of subsets make power set 2^n_elements   list out(pwrset_card);          // list output   int listidx = 0;                // count through list indeces   out[0] = charactervector::create(); // first element of list represents empty set   charactervector tmp;            // hold new extended vector    (int i=0; < n_els; ++i) {     (int j=0; j <= listidx; ++j) {        listidx++;       tmp = out[j];       tmp.push_back(els[i]);       out[listidx] = tmp;      }   }   return out; } 

but!

> pwr_set_cpp(letters[1:3]) 

gives me error: attempt set index 8/8 in set_vector_elt

googling , looking @ source code here leads me think trying index beyond set_vector_elt has cached? must mean mis-understand how step through input/output loops in rcpp or of sort.

any guidance in helping me understand here wonderful. ahead of time.

update: fix.

as per answer/comments @romain francois , @nicola key misunderstanding way step through loops in r sorta clever! (or @ least appreciate more before). implement same thing in c++ have break listidx counter variable (which condition check j) , interim cnt2 records number of j steps taken on top of current counter state. counter gets updated after passing each exit current value of cnt2.

#include <rcpp.h> #include <math.h> using namespace rcpp;  // [[rcpp::export]] list pwr_set_cpp(charactervector els) {    int n_els = els.size();            int pwrset_card = pow(2,n_els);    list out(pwrset_card);             out[0] = stringvector::create();    charactervector tmp;               int counter = 0;   (int i=0; < n_els; ++i) {     int cnt2 = counter;            // capture counter state       (int j =0; j <= counter; ++j) {         cnt2++;                   // capture counter + j steps         tmp = as<stringvector>(out[j]);         tmp.push_back(as<std::string>(els[i]));         out[cnt2] = tmp;      }       counter = cnt2;             // update counter state   }   return out; } 

quick timings

just fun little benchmark. although i'm sure there more efficient ways (with same algorithm structure) i'm doing lot of copying of strsxp elements/vectors.

x <- letters[1:18] pwr_set_bitecompile <- compiler::cmpfun(pwr_set) # r 3.2.0 ! microbenchmark::microbenchmark(     pwr_set(x),     pwr_set_bitecompile(x),     pwr_set_cpp(x))  unit: milliseconds                    expr      min       lq     mean   median       uq       max neval              pwr_set(x) 748.6553 820.0667 841.2828 834.1229 856.2436 1023.1324   100  pwr_set_bitecompile(x) 365.9969 480.9474 498.2100 503.5115 518.8562  596.8205   100          pwr_set_cpp(x) 155.9447 283.8771 295.8411 300.4865 314.0826  342.0261   100 

the problem trying assign out[8] , that's above number of elements in list.

see added line:

  rprintf( "out.size() = %d, listidx = %d\n", out.size(), listidx );   out[listidx] = tmp; 

you'll get:

> pwr_set_cpp(letters[1:3]) out.size() = 8, listidx = 1 out.size() = 8, listidx = 2 out.size() = 8, listidx = 3 out.size() = 8, listidx = 4 out.size() = 8, listidx = 5 out.size() = 8, listidx = 6 out.size() = 8, listidx = 7 out.size() = 8, listidx = 8 error in pwr_set_cpp(letters[1:3]) :   tentative de modification de l'index 8/8 dans set_vector_elt calls: sourcecpp ... withvisible -> eval -> eval -> pwr_set_cpp -> <anonymous> exécution arrêtée       

see comment @nicola. you're doing wrong listidx , j. if overflow did not stop it, you'd endless loop.

what's confusing r code:

for(j in 1l:listidx){   listidx <- listidx + 1l   out[[listidx]] <- c(out[[j]], els[i]) } 

evaluates 1l:listidx once, inside loop, can use listidx else. that's not case in c++.