Updating the `STL random_shuffle for permutations` article

[K-Maehashi]

Hello, I found random_shufle() used in STL random_shuffle for permutations was not available in C++17. The following code returns the same result, and I thought it would be helpful for other users. Since this is a minor change to the article, I opened this issue instead of sending a pull request.

#include <Rcpp.h>

inline int randWrapper(const int n) { return floor(unif_rand()*n); }

// [[Rcpp::export]]
Rcpp::NumericVector randomShuffle(Rcpp::NumericVector a) {

    // clone a into b to leave a alone
    Rcpp::NumericVector b = Rcpp::clone(a);
    int n = b.size();
    int j;

    // Fisher-Yates Shuffle Algorithm
    for (int i = 0; i < n - 1; i++)
    {
      j = i + randWrapper(n - i);
      std::swap(b[i], b[j]);
    }
    return b;
}

Test

sourceCpp(code =
'
#include <Rcpp.h>

inline int randWrapper(const int n) { return floor(unif_rand()*n); }

// [[Rcpp::export]]
Rcpp::NumericVector randomShuffle_1(Rcpp::NumericVector a) {  // Currently on Rcpp Gallery

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

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

    return b;
}

// [[Rcpp::export]]
Rcpp::NumericVector randomShuffle_2(Rcpp::NumericVector a) {

    // clone a into b to leave a alone
    Rcpp::NumericVector b = Rcpp::clone(a);
    int n = b.size();
    int j;

    // Fisher-Yates Shuffle Algorithm
    for (int i = 0; i < n - 1; i++)
    {
      j = i + randWrapper(n - i);
      std::swap(b[i], b[j]);
    }
    return b;
}
'
)

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

[eddelbuettel]

Thanks so much! I'll probably just update the article to using C++17 because (for technical reasons) we can only compile each post as 'one unit'.

[eddelbuettel]

On the other hand, we see that std::shuffle is available now or so it states. I actually cannot get g++ to fail here even in C++17 or C++20 modes. And the warning only comes from clang++. Weird.

[eddelbuettel]

BTW I get consistently

> randomShuffle(a) 
[1] 1 4 3 7 5 8 6 2 
>

on the existing one but always

> randomShuffle2(a)   
[1] 8 1 4 2 7 5 3 6   
>

so it is not really a drop-in replacement offering identical outcomes.

[K-Maehashi]

Hi @eddelbuettel thank you so much for updating the document.

To your second comment:
I used the following code and all of them (random_shuffle(), C++11 random_shuffle(), C++17 manual implementation, and C++11 manual implementation) returned the same vector 8 1 4 2 7 5 3 6. In other words, I did not get 1 4 3 7 5 8 6 2 even though I followed your original code.

I could not figure out where this difference came from, unfortunately. I initially thought it was because R changed the random number generation from R 3.6 and your original post was from 2012, but your new article has the same result, 1 4 3 7 5 8 6 2.

library(Rcpp)

# Original
sourceCpp(code =
'
#include <Rcpp.h>

inline int randWrapper(const int n) { return floor(unif_rand()*n); }

// [[Rcpp::export]]
Rcpp::NumericVector randomShuffle(Rcpp::NumericVector a) {

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

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

    return b;
}
'
)

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

# C++11
sourceCpp(code =
'
#include <Rcpp.h>
// [[Rcpp::plugins("cpp11")]]
inline int randWrapper(const int n) { return floor(unif_rand()*n); }

// [[Rcpp::export]]
Rcpp::NumericVector randomShuffle_cpp11(Rcpp::NumericVector a) {

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

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

    return b;
}
'
)

set.seed(42)
randomShuffle_cpp11(a)  # 8 1 4 2 7 5 3 6
set.seed(42)
randomShuffle_cpp11(a)

# C++17
sourceCpp(code =
'
#include <Rcpp.h>
using namespace std;

// [[Rcpp::plugins("cpp17")]]

inline int randWrapper(const int n) { return floor(unif_rand()*n); }

// [[Rcpp::export]]
Rcpp::NumericVector randomShuffle_cpp17(Rcpp::NumericVector a) {

    // clone a into b to leave a alone
    Rcpp::NumericVector b = Rcpp::clone(a);
    int n = b.size();
    int j;

    for (int i = 0; i < n - 1; i++)
    {
      j = i + randWrapper(n - i);
      std::swap(b[i], b[j]);
    }
    return b;
}
'
)

set.seed(42)
randomShuffle_cpp17(a)
set.seed(42)
randomShuffle_cpp17(a)

# New code under cpp11
sourceCpp(code =
'
#include <Rcpp.h>
using namespace std;

// [[Rcpp::plugins("cpp11")]]

inline int randWrapper(const int n) { return floor(unif_rand()*n); }

// [[Rcpp::export]]
Rcpp::NumericVector randomShuffle_cpp11_2(Rcpp::NumericVector a) {

    // clone a into b to leave a alone
    Rcpp::NumericVector b = Rcpp::clone(a);
    int n = b.size();
    int j;

    for (int i = 0; i < n - 1; i++)
    {
      j = i + randWrapper(n - i);
      std::swap(b[i], b[j]);
    }
    return b;
}
'
)

set.seed(42)
randomShuffle_cpp11_2(a)
set.seed(42)
randomShuffle_cpp11_2(a)

My environment info, if it helps:

> sessionInfo()                                                                                                                                                                                           
R version 4.1.2 (2021-11-01)
Platform: aarch64-apple-darwin20 (64-bit)
Running under: macOS Monterey 12.1

Matrix products: default
BLAS:   /Library/Frameworks/R.framework/Versions/4.1-arm64/Resources/lib/libRblas.0.dylib
LAPACK: /Library/Frameworks/R.framework/Versions/4.1-arm64/Resources/lib/libRlapack.dylib

locale:
[1] en_US.UTF-8/en_US.UTF-8/en_US.UTF-8/C/en_US.UTF-8/en_US.UTF-8

attached base packages:
[1] stats     graphics  grDevices utils     datasets  methods   base     

other attached packages:
[1] Rcpp_1.0.7

loaded via a namespace (and not attached):
[1] compiler_4.1.2 cli_3.5.0      tools_4.1.2    jsonlite_1.7.2 rlang_1.0.6  

[eddelbuettel]

Yes, same suspicion here, and I did similar exercises. It is apperently not R 3.6.* and the change in the RNG used for sampling. I guess I still publish what I have drafted here and simply note the difference.

BTW I can only credit you here as "GitHub user @K-Maehashi" and I usually use full names of people who contribute. Could you share your full name and/or how you would prefer to see it in writing?

[K-Maehashi]

Yes, same suspicion here, and I did similar exercises. It is apperently not R 3.6.* and the change in the RNG used for sampling. I guess I still publish what I have drafted here and simply note the difference.

Thank you for taking extra steps and trying it. It's pretty mysterious because I understood R's RNG returned the same value across platforms. And yes, I agree updating the article with the note will benefit Rcpp users with the C++17 setting.

Could you share your full name and/or how you would prefer to see it in writing?

Sure! If you need the full name, please use "Kenta Maehashi".

[eddelbuettel]

Thanks, posted, and should update at GitHub soon. Appreciate raising the issue and the suggestion.

As this issue is addressed, closing it now. Feel free to reopen or comment as needed. Thanks again!