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.

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\).

#include <iostream> #include <random> #include <utility> namespace { // make a random number generator std::random_device r; std::default_random_engine eng(r()); } //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. } void print(int data[], int n) { for (int i = 0; i<n; ++i) { std::cout << data[i] << '\t'; } std::cout << std::endl; } int main() { int data[] = {1,1,2,3,5,8,13,21,34}; for (int i = 0; i<5; ++i) { permute(data, 9); print(data, 9); } std::cout << '\n'; }

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.

#include <algorithm> #include <iostream> #include <iterator> #include <random> namespace { std::random_device r; std::default_random_engine eng(r()); // make a random number generator } void print(int data[], int n) { for (int i = 0; i<n; ++i) { std::cout << data[i] << '\t'; } std::cout << std::endl; } int main() { int data[] = {1,1,2,3,5,8,13,21,34}; for (int i = 0; i<5; ++i) { std::shuffle(std::begin(data), std::end(data), eng); print(data, 9); } std::cout << std::endl; }

More to Explore

• From cppreference.com

  • Random number generation and random_shuffle

  • Common math functions

  • is_permuation and next_permuation

Acknowledgements

This section is adapted from Open Data Structures (OpenDSA) by Ville Karavirta and Cliff Shaffer which is distributed under the MIT License.

You have attempted of activities on this page