Storing all Possible Permutations within R

Question

I am using permutations command under "gtools". However, it produced memory problem.

I have tried the following:

library(gtools)
permutations(n=15,r=8)

However, I have got the following error message:

 Error in next_permutations(n, k, -1L, NULL, x, freq, replace, type) : 
cannot allocate vector of length 2075673600.

This is very basic of what I am doing. I need permutations lot more than n=15 and k=8.

Answer 1

My previous answer had two short-comings:

• It did only compute permutations of 1:r.
• The number of permutations was wrong, since I used n! / r! instead of n! / (n - r)!.

The last point increases the size of the resulting matrix for n = 15 and r = 8 by a factor of 8 to about 8 GB. this highlights the point made by Ben Bolker in the comments: One should think about working through the permutations in an iterative fashion.

Anyway, a simple way to generate all permutations is to generate all combinations with combn() first. After that one can generate the permutations for each combination using std::next_permutation in C++:

src1 <- '
IntegerMatrix permute_combinations(const IntegerMatrix& combs) {
  size_t numComb(combs.cols());
  size_t r(combs.rows());
  size_t numPermPerComb(1);
  for(size_t i = 1; i <= r; ++i) numPermPerComb *= i;
  size_t numPerm = numComb * numPermPerComb;
  IntegerMatrix perms(numPerm, r);

  for(size_t i = 0; i < numComb; ++i) {
    IntegerVector v = combs(_, i);
    for (size_t j = 0; j < numPermPerComb; ++j) {
      perms(i * numPermPerComb + j, _) = v;
      std::next_permutation(v.begin(), v.end());
    }
  }
  return perms;
}
'

Rcpp::cppFunction(src1)
system.time(perms <- permute_combinations(combn(15, 8)))
#>        User      System verstrichen 
#>      54.572       1.136      56.006
dim(perms)
#> [1] 259459200         8
object.size(perms)
#> 8302694600 bytes
head(perms)
#>      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
#> [1,]    1    2    3    4    5    6    7    8
#> [2,]    1    2    3    4    5    6    8    7
#> [3,]    1    2    3    4    5    7    6    8
#> [4,]    1    2    3    4    5    7    8    6
#> [5,]    1    2    3    4    5    8    6    7
#> [6,]    1    2    3    4    5    8    7    6
tail(perms)
#>              [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
#> [259459195,]   15   14   13   12   11    8    9   10
#> [259459196,]   15   14   13   12   11    8   10    9
#> [259459197,]   15   14   13   12   11    9    8   10
#> [259459198,]   15   14   13   12   11    9   10    8
#> [259459199,]   15   14   13   12   11   10    8    9
#> [259459200,]   15   14   13   12   11   10    9    8

Original version

The resulting matrix is just below 1 GB, so there has to be some inefficiency in the gtools code. Here a quick & dirty C++ version for usage with Rcpp:

src <- 'IntegerMatrix permutations(int n, int r) {
  size_t numPerm(1);
  for(int i = n; i > r; --i) {
    numPerm *= i;
  }
  IntegerMatrix result(numPerm, r);

  IntegerVector v(r);
  std::iota (std::begin(v), std::end(v), 1);

  for (size_t i = 0; i < numPerm; ++i) {
    result(i, _) = v;
    std::next_permutation(v.begin(), v.end());
  }
  return result;
}'
Rcpp::cppFunction(src)
system.time(perms <- permutations(15, 8))
#>        User      System verstrichen 
#>       6.909       0.060       6.970
dim(perms)
#> [1] 32432400        8
object.size(perms)
#> 1037837000 bytes
head(perms)
#>      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
#> [1,]    1    2    3    4    5    6    7    8
#> [2,]    1    2    3    4    5    6    8    7
#> [3,]    1    2    3    4    5    7    6    8
#> [4,]    1    2    3    4    5    7    8    6
#> [5,]    1    2    3    4    5    8    6    7
#> [6,]    1    2    3    4    5    8    7    6