..  Copyright (C)  Dave Parillo.  Permission is granted to copy, distribute
    and/or modify this document under the terms of the GNU Free Documentation
    License, Version 1.3 or any later version published by the Free Software
    Foundation; with Invariant Sections being Forward, and Preface,
    no Front-Cover Texts, and no Back-Cover Texts.  A copy of
    the license is included in the section entitled "GNU Free Documentation
    License".
.. This file is adapted from the OpenDSA eTextbook project. See
.. http://opendsa.org for more details.
.. Copyright (c) 2012-2020 by the OpenDSA Project Contributors, and
.. distributed under an MIT open source license.

.. index::
   single: permutations
   single: random uniform_int_distribution
   single: random shuffle
   single: shuffle

.. _random-numbers-permutations:

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

.. tb-group::
   :name: permute

   .. tb-tab:: permute

      Sometimes one would like to obtain a random permutation for a
      sequence, that is, one of the :math:`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:

      .. code-block:: cpp

         //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 :math:`size-1` of vector ``data``.
      Function :utility:`swap`
      exchanges elements in ``data``,
      and :numeric:`uniform_int_distribution <random/uniform_int_distribution>`
      returns an integer value uniformly distributed 
      in the range 0 to :math:`i-1`.

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

   .. tb-tab:: Run It

      .. tb-code:: cpp
         :name: math_permute_ac
         :caption: Example math_permute_ac

         #include <cstddef>
         #include <iostream>
         #include <random>
         #include <utility>
         #include <vector>

         using std::size_t;

         //Randomly permute the values in array
         void permute(std::vector<int>& data) {
           std::random_device r;
           std::default_random_engine eng(r());
           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.
         }

         void print(const std::vector<int>& data) {
           for(const int& value: data) {
             std::cout << value << '\t';
           }
           std::cout << '\n';
         }

         int main() {
           std::vector<int> data = {1,1,2,3,5,8,13,21,34};

           for (int i = 0; i<5; ++i) {
             permute(data);
             print(data);
           }
           return 0;
         }

   .. tb-tab:: shuffle

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

      .. code-block:: cpp

         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.

   .. tb-tab:: Run shuffle

      .. tb-code:: cpp
         :name: math_permute_shuffle_ac
         :caption: Example math_permute_shuffle_ac

         #include <algorithm>
         #include <cstddef>
         #include <iostream>
         #include <iterator>
         #include <random>

         namespace {
           std::random_device r;
           std::default_random_engine eng(r());  // make a random number generator
         }

         void print(const std::vector<int>& data) {
           for(const int& value: data) {
             std::cout << value << '\t';
           }
           std::cout << '\n';
         }

         int main() {
           std::vector<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);
           }
           return 0;
         }

.. admonition:: More to Explore

   - From cppreference.com

     - :numeric:`Random number generation <random>` and
       :algorithm:`random_shuffle`
     - :numeric:`Common math functions <math>`
     - :algorithm:`is_permuation` and :algorithm:`next_permuation` 

.. topic:: Acknowledgements

   This section is adapted from 
   `Open Data Structures (OpenDSA) <https://opendsa-server.cs.vt.edu>`__
   by Ville Karavirta and Cliff Shaffer
   which is distributed under the `MIT License <https://github.com/OpenDSA/OpenDSA/blob/master/MIT-license.txt>`__.