# Exceedingly Simple Permutations and Combinations
Jan de Leeuw
Version 002, Februari 23, 2016
Note: This is a working paper which will be expanded/updated frequently. The directory [gifi.stat.ucla.edu/nextPC](http://gifi.stat.ucla.edu/nextpc has a pdf copy of this article, the complete Rmd file with all code chunks, and the R and C source code.
#Problem
Most permutation and combination function in the various `R` packages generate a list or matrix with all permutations of order $n$ or all choices of $m$ from $n$ objects. If $n$ is large the list or matrix will be large and to fill it will take a lot of time. Usually you will need the permutations or combinations for some higher purpose, and you just sit there twiddling your thumbs while the matrix or list is constructed, or while your `R` memory is filled to the point of exploding.
In this note we give simple functions, using the `.C` interface, to compute the next permutation or combination in the lexicographic order.
The functions take a vector argument and return a vector. You could store the returned values in a matrix or list, but for some applications it makes more sense to use and discard them. That obviously saves memory. For an application of the permutation function, see @deleeuw_C_05h, for an application of the combination function see @deleeuw_groenen_mair_E_16f.
To fill a matrix or list we would have to use these functions in an `R` loop, so they probably are not too efficient in terms of time. We sacrifice time to gain memory. On the other hand, using the `nextPermutation()` and `nextCombination()` functions will be easy to parallelelize.
#Examples
```r
nextPermutation (1:3)
```
```
## [1] 1 3 2
```
```r
nextPermutation (c(1,3,2))
```
```
## [1] 2 1 3
```
```r
nextPermutation (nextPermutation (c(1,3,2)))
```
```
## [1] 2 3 1
```
```r
nextPermutation (3:1)
```
```
## NULL
```
```r
nextCombination(1:3,5)
```
```
## [1] 1 2 4
```
```r
nextCombination(c(1,4,5), 5)
```
```
## [1] 2 3 4
```
```r
nextCombination(nextCombination(c(1,4,5), 5), 5)
```
```
## [1] 2 3 5
```
```r
nextCombination(3:5,5)
```
```
## NULL
```
#Code
##C
```c
void
swap(int *x, int i, int j)
{
int temp;
temp = x[i];
x[i] = x[j];
x[j] = temp;
}
void
nextPermutation (int *x, int *nn)
{
int i, j, n = *nn;
i = n - 1;
while (x[i - 1] >= x[i])
i--;
if (i == 0)
return;
j = n;
while (x[j - 1] <= x[i - 1])
j--;
swap(x, i - 1, j - 1);
j = n;
i++;
while (i < j) {
swap(x, i - 1, j - 1);
j--;
i++;
}
}
void nextCombination (int* n, int* m, int* next) {
int i, j, mm = *m - 1, nn = *n;
for (i = mm; i >= 0; i--) {
if (next[i] != nn - mm + i) {
next[i]++;
if (i < mm) {
for (j = i + 1; j <= mm; j++)
next[j] = next[j - 1] + 1;
}
return;
}
}
}
```
## R
```r
dyn.load("nextPC.so")
nextPermutation <- function (x) {
if (all (x == (length(x):1))) return (NULL)
z <- .C("nextPermutation", as.integer(x), as.integer(length(x)))
return (z[[1]])
}
nextCombination <- function (x, n) {
m <- length (x)
if (all (x == ((n - m) + 1:m))) return (NULL)
z <- .C("nextCombination", as.integer(n), as.integer (m), as.integer(x))
return (z[[3]])
}
```
#NEWS
001 02/22/16
* First release
002 02/23/16
* Added some verbiage
* Added references to MDS applications
#References