PermutationsΒΆ

A permutation of a sequence \(\mathbf{S}\) is simply the members of \(\mathbf{S}\) arranged in some order. For example, a permutation of the integers 1 through \(n\) would be those values arranged in some order. If the sequence contains \(n\) distinct members, then there are \(n!\) different permutations for the sequence. This is because there are \(n\) choices for the first member in the permutation; for each choice of first member there are \(n-1\) choices for the second member, and so on.

permute

Sometimes one would like to obtain a random permutation for a sequence, that is, one of the \(n!\) possible permutations is selected in such a way that each permutation has equal probability of being selected. A simple function for generating a random permutation is as follows.

//Randomly permute the values in array
void permute(int data[], int n) {
  for (int i = n; i > 0; --i) {
    int j = std::uniform_int_distribution<int> {0, i-1} (eng);
    std::swap(data[i-1], data[j]);  // swap data[i-1] with a random
  }                                 // position in the range 0 to i-1.
}

Here, the \(n\) values of the sequence are stored in positions 0 through \(n-1\) of array data. Function swap exchanges elements in array data, and uniform_int_distribution returns an integer value uniformly distributed in the range 0 to \(i-1\).

Run It

 1#include <iostream>
 2#include <random>
 3#include <utility>
 4
 5namespace {
 6  // make a random number generator
 7  std::random_device r;
 8  std::default_random_engine eng(r());
 9}
10
11//Randomly permute the values in array
12void permute(int data[], int n) {
13  for (int i = n; i > 0; --i) {
14    int j = std::uniform_int_distribution<int> {0, i-1} (eng);
15    std::swap(data[i-1], data[j]);  // swap data[i-1] with a random
16  }                                 // position in the range 0 to i-1.
17}
18void print(int data[], int n) {
19  for (int i = 0; i<n; ++i) {
20    std::cout << data[i] << '\t';
21  }
22  std::cout << std::endl;
23}
24int main() {
25  int data[] = {1,1,2,3,5,8,13,21,34};
26
27  for (int i = 0; i<5; ++i) {
28    permute(data, 9);
29    print(data, 9);
30  }
31  std::cout << '\n';
32}

shuffle

Randomly shuffling a range of data is a common enough activity that it is implemented in the standard library. The shuffle function does what our permute function does, but a bit more generically.

std::shuffle(std::begin(data), std::end(data), eng);

Instead of an entire array it takes a range of data and a random number generator.

Run shuffle

 1#include <algorithm>
 2#include <iostream>
 3#include <iterator>
 4#include <random>
 5
 6namespace {
 7  std::random_device r;
 8  std::default_random_engine eng(r());  // make a random number generator
 9}
10
11void print(int data[], int n) {
12  for (int i = 0; i<n; ++i) {
13    std::cout << data[i] << '\t';
14  }
15  std::cout << std::endl;
16}
17int main() {
18  int data[] = {1,1,2,3,5,8,13,21,34};
19
20  for (int i = 0; i<5; ++i) {
21    std::shuffle(std::begin(data), std::end(data), eng);
22    print(data, 9);
23  }
24  std::cout << std::endl;
25}

More to Explore