STL random_shuffle for permutations

December 30, 2012
By

(This article was first published on Rcpp Gallery, and kindly contributed to R-bloggers)

The STL also contains random sampling and shuffling algorithms. We start by looking at random_shuffle.

There are two forms. The first uses an internal RNG with its own seed; the second form allows for a function object conformant to the STL’s requirements (essentially, given N produce a uniform draw greater or equal to zero and less than N). This is useful for us as it lets us tie this to the same RNG which R uses.

#include <Rcpp.h>

// wrapper around R's RNG such that we get a uniform distribution over
// [0,n) as required by the STL algorithm
inline int randWrapper(const int n) { return floor(unif_rand()*n); }

// [[Rcpp::export]]
Rcpp::NumericVector randomShuffle(Rcpp::NumericVector a) {
    // already added by sourceCpp(), but needed standalone
    Rcpp::RNGScope scope;             

    // clone a into b to leave a alone
    Rcpp::NumericVector b = Rcpp::clone(a);

    std::random_shuffle(b.begin(), b.end(), randWrapper);

    return b;
}

We can illustrate this on a simple example or two:

a <- 1:8
set.seed(42)
randomShuffle(a)
[1] 1 4 3 7 5 8 6 2
set.seed(42)
randomShuffle(a)
[1] 1 4 3 7 5 8 6 2

By tieing the STL implementation of the random permutation to the RNG from R, we are able to compute reproducible permutations, fast and from C++.

To leave a comment for the author, please follow the link and comment on his blog: Rcpp Gallery.

R-bloggers.com offers daily e-mail updates about R news and tutorials on topics such as: visualization (ggplot2, Boxplots, maps, animation), programming (RStudio, Sweave, LaTeX, SQL, Eclipse, git, hadoop, Web Scraping) statistics (regression, PCA, time series, trading) and more...



If you got this far, why not subscribe for updates from the site? Choose your flavor: e-mail, twitter, RSS, or facebook...

Comments are closed.