11.8. 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 this:

//Randomly permute the values in vector
void permute(vector<int>& data) {
  for (std::size_t i = data.size(); i > 0; --i) {
    std::size_t j = std::uniform_int_distribution<std::size_t> {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 values of the sequence are stored in positions 0 through \(size-1\) of vector data. Function swap exchanges elements in data, and uniform_int_distribution returns an integer value uniformly distributed in the range 0 to \(i-1\).

Note we are not passing the vector by const& so that we can modify it.

Run It

Example math_permute_ac
 1#include <cstddef>
 2#include <iostream>
 3#include <random>
 4#include <utility>
 5#include <vector>
 6
 7using std::size_t;
 8
 9//Randomly permute the values in array
10void permute(std::vector<int>& data) {
11  std::random_device r;
12  std::default_random_engine eng(r());
13  for (std::size_t i = data.size(); i > 0; --i) {
14    std::size_t j = std::uniform_int_distribution<std::size_t> {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}
18
19void print(const std::vector<int>& data) {
20  for(const int& value: data) {
21    std::cout << value << '\t';
22  }
23  std::cout << '\n';
24}
25
26int main() {
27  std::vector<int> data = {1,1,2,3,5,8,13,21,34};
28
29  for (int i = 0; i<5; ++i) {
30    permute(data);
31    print(data);
32  }
33  return 0;
34}

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 container it takes a range of data and a random number generator.

Run shuffle

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

More to Explore