//  (C) Copyright Ben Bear, Herve Bronnimann 2007.
//  Use, modification and distribution are subject to the
//  Boost Software License, Version 1.0. (See accompanying file
//  LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)

#include <algorithm>
#include <functional>
#include <iostream>
#include <list>
#include <numeric>
#include <utility>
#include <vector>

// #include <boost/config.hpp>
#include <boost/algorithm/combination.hpp>

using namespace boost;

void next_partial_permutation_ex() {
    std::cout << "\nExamplifying next_partial_permutation."
              << "\n--------------------------------------" << std::endl;

// Enumerating all the subsequences of a given size:
//--------------------------------------------------
// Given a set '{ 0, 1, . . . n -1 }' of size 'n', we wish to enumerate all the
// permutations of size 'r <= n' that have no repetitions.  We know before-hand
// that there are 'n! / (n-r)!' such permutations.  Enumerating them is easy
// using the 'next_partial_permutation' algorithm:
//..
    const int r = 3;
    const int n = 6;

    std::vector<int> v(n);
    for (int i = 0; i < n; ++i) v[i] = i;
       
    int N = 0;
    do {
        ++N;
        if (N < 8 || N > 113) {
            std::cout << "[ " << v[0];
            for (int j = 1; j < r; ++j) { std::cout << ", " << v[j]; }
            std::cout << "  ]" << std::endl;
        } else if (N == 8) {
            std::cout << "  . . ." << std::endl;
        }
    } while (next_partial_permutation(v.begin(), v.begin() + r, v.end()));
    std::cout << "Found " << N << " permutations of size 3 without repetitions"
              << " from a set of size 5." << std::endl;
//..
// This code will print out:
//..
//  [ 0, 1, 2 ]
//  [ 0, 1, 3 ]
//  [ 0, 1, 4 ]
//  [ 0, 1, 5 ]
//  [ 0, 2, 1 ]
//  [ 0, 2, 3 ]
//  [ 0, 2, 4 ]
//    .  .  .
//  [ 5, 3, 2 ]
//  [ 5, 3, 4 ]
//  [ 5, 4, 0 ]
//  [ 5, 4, 1 ]
//  [ 5, 4, 2 ]
//  [ 5, 4, 3 ]
//  Found 120 permutations of size 3 without repetitions from a set of size 5.
//..
// The situation is a bit more complex to understand when the original sequence
// has duplicate values, because the notion of permutation without repetitions
// in this case consists of the subsequences indexed by all collections of
// *distinct* 'r' indices among the 'n' indices, with identical such subsequences
// enumerated only once.  Suppose for instance that 'v' contains the sequence
// '{ 0, 1, 2, 0, 1, 3 }'.  In order to start the enumeration, the sequence
// must first be sorted into '{ 0, 0, 1, 1, 2, 3 }', then all the sequence of
// distinct three indices (permutations of size 'r' of '{ 0, . . .  n - 1 }')
// are applied to the above sequence, but notice for instance that the first
// two sequence of indices generate the same permutation '[ 0, 0, 1 ]' since
// the original sequence has the same element at indices 2 and 3.  This
// subsequence is enumerated only once.  Here is the code (identical, except
// for the initialization of 'v'):
//..
    v[0] = 0; v[1] = 1; v[2] = 2; v[3] = 0; v[4] = 1; v[5] = 3; 
    std::sort(v.begin(), v.end());
       
    N = 0;  // note: r and n are still 3 and 6, respectively
    do {
        ++N;
        std::cout << "[ " << v[0];
        for (int j = 1; j < r; ++j) { std::cout << ", " << v[j]; }
        std::cout << "  ]" << std::endl;
    } while (next_partial_permutation(v.begin(), v.begin() + r, v.end()));
    std::cout << "Found " << N << " permutations of size 3 without repetitions"
              << " from a (multi)set of size 5." << std::endl;
//..
// This time, the code outputs the much shorter:
//..
//  [ 0,  0,  1  ]
//  [ 0,  0,  2  ]
//  [ 0,  0,  3  ]
//  [ 0,  1,  0  ]
//  [ 0,  1,  1  ]
//  [ 0,  1,  2  ]
//  [ 0,  1,  3  ]
//  [ 0,  2,  0  ]
//  [ 0,  2,  1  ]
//  [ 0,  2,  3  ]
//  [ 0,  3,  0  ]
//  [ 0,  3,  1  ]
//  [ 0,  3,  2  ]
//  [ 1,  0,  0  ]
//  [ 1,  0,  1  ]
//  [ 1,  0,  2  ]
//  [ 1,  0,  3  ]
//  [ 1,  1,  0  ]
//  [ 1,  1,  2  ]
//  [ 1,  1,  3  ]
//  [ 1,  2,  0  ]
//  [ 1,  2,  1  ]
//  [ 1,  2,  3  ]
//  [ 1,  3,  0  ]
//  [ 1,  3,  1  ]
//  [ 1,  3,  2  ]
//  [ 2,  0,  0  ]
//  [ 2,  0,  1  ]
//  [ 2,  0,  3  ]
//  [ 2,  1,  0  ]
//  [ 2,  1,  1  ]
//  [ 2,  1,  3  ]
//  [ 2,  3,  0  ]
//  [ 2,  3,  1  ]
//  [ 3,  0,  0  ]
//  [ 3,  0,  1  ]
//  [ 3,  0,  2  ]
//  [ 3,  1,  0  ]
//  [ 3,  1,  1  ]
//  [ 3,  1,  2  ]
//  [ 3,  2,  0  ]
//  [ 3,  2,  1  ]
//  Found 42 permutations of size 3 without repetitions of a (multi)set of size 5.
//..
// Note that if we had wanted the permutations that had no repetitions of
// values (as opposed to repetitions of indices), we could simply have
// removed the duplicates from 'v', yielding a short sequence of 'm' values,
// and enumerated the permutations of 'r' elements taken from these 'm' values
// without repetitions.  Here 'm' would be 4, and there would be four such
// permutations.
}

void next_combination_ex() {
    std::cout << "\nExamplifying next_combination(first, middle, last)."
              << "\n---------------------------------------------------" << std::endl;

// Enumeration all the subsets of a given size:
//---------------------------------------------
// Given a set '{ 0, 1, . . . n -1 }', we wish to enumerate all the subsets of
// size 'r <= n'.  This is easy using the 'next_combination' algorithm that
// takes three or four arguments:
//..
    const int r = 3;
    const int n = 10;
    std::vector<int> v_int(n);
    for (int i = 0; i < n; ++i) { v_int[i] = i; }
       
    int N = 0;
    do {
        ++N;
        if (N < 10 || N > 117) {
            std::cout << "[ " << v_int[0];
            for (int j = 1; j < r; ++j) { std::cout << ", " << v_int[j]; }
            std::cout << " ]" << std::endl;
        } else if (N == 10) {
            std::cout << "  . . ." << std::endl;
        }
    } while (next_combination(v_int.begin(), v_int.begin() + r, v_int.end()));
    std::cout << "Found " << N << " combinations of size " << r << " without repetitions"
              << " from a set of " << n << " elements." << std::endl;
//..
// This code will print out:
//..
//  [ 0, 1, 2 ]
//  [ 0, 1, 3 ]
//  [ 0, 1, 4 ]
//  [ 0, 1, 5 ]
//  [ 0, 1, 6 ]
//  [ 0, 1, 7 ]
//  [ 0, 1, 8 ]
//  [ 0, 1, 9 ]
//  [ 0, 2, 3 ]
//    .  .  .
//  [ 6, 7, 9 ]
//  [ 6, 8, 9 ]
//  [ 7, 8, 9 ]
//  Found 120 combinations of size 3 without repetitions from a set of 10 elements.
//..
// Had some elements been equal, e.g., 'v = { 0, 1, 2, 3, 1, 2, 3, 1, 2, 3 }',
// we would have had the following output instead (the discussion is the same
// as for permutations without repetitions, except that the sequences in the
// output must be sorted):
//..
//  [ 0, 1, 1 ]
//  [ 0, 1, 2 ]
//  [ 0, 1, 3 ]
//  [ 0, 2, 2 ]
//  [ 0, 2, 3 ]
//  [ 0, 3, 3 ]
//  [ 1, 1, 1 ]
//  [ 1, 1, 2 ]
//  [ 1, 1, 3 ]
//  [ 1, 2, 2 ]
//  [ 1, 2, 3 ]
//  [ 1, 3, 3 ]
//  [ 2, 2, 2 ]
//  [ 2, 2, 3 ]
//  [ 2, 3, 3 ]
//  [ 3, 3, 3 ]
//  Found 16 combinations of size 3 without repetitions from a (multi)set of 10 elements.
//..
// For verification, here is the code below (do not forget to sort the vector
// initially!):
//..
    const int V[] = { 0, 1, 2, 3, 1, 2, 3, 1, 2, 3 }; 
    v_int.assign(V, V + n);
    std::sort(v_int.begin(), v_int.end());

    N = 0;
    do {
        ++N;
        std::cout << "[ " << v_int[0];
        for (int j = 1; j < r; ++j) { std::cout << ", " << v_int[j]; }
        std::cout << "  ]" << std::endl;
    } while (next_combination(v_int.begin(), v_int.begin() + r, v_int.end()));
    std::cout << "Found " << N << " combinations of size " << r << " without repetition"
              << " from a (multi)set of " << n << " elements." << std::endl;
//..
// Suppose we have a slightly different requirement, with a type that cannot be
// swapped, either because it isn't efficient, or because the sequence cannot
// be permuted (if it is passed 'const', for instance).  For expository
// purposes, we use a non-modifiable vector of 'std::string'.  In this case we
// can apply the previous solution with an extra level of indirection, and
// apply 'next_combination' to a vector that holds iterators into our
// non-modifiable vector of strings (note that the iterators are in sorted
// order):
//..
    const char *strings[] = {
        "one", "two", "three", "four", "five", "six", "seven", "eight", "nine", "ten"
    };
    const int m = sizeof strings / sizeof *strings;
    std::vector<std::string> V_strings(strings, strings + m);
    const std::vector<std::string>& v_strings = V_strings;
       
    std::vector<std::vector<std::string>::const_iterator> w(m);
    for (int i = 0; i < m; ++i) { w[i] = v_strings.begin() + i; }

    N = 0;  // note: r and n are still 3 and 10, respectively
    do {
        ++N;
        if (N < 9 || N > 115) {
            std::cout << "[ " << *w[0];
            for (int j = 1; j < r; ++j) { std::cout << ", " << *w[j]; }
            std::cout << "  ]" << std::endl;
        } else if (N == 9) {
            std::cout << "  . . ." << std::endl;
        }
    } while (next_combination(w.begin(), w.begin() + r, w.end()));
    std::cout << "Found " << N << " combinations of size " << r << " without repetition"
              << " from a set of " << n << " elements." << std::endl;
//..
// This prints out, while *never* modifying the value of 'v':
//..
//  [ one, two, three ]
//  [ one, two, four ]
//  [ one, two, four ]
//  [ one, two, five ]
//  [ one, two, seven ]
//  [ one, two, eight ]
//  [ one, two, nine ]
//  [ one, two, ten ]
//  [ one, three, four ]
//    .  .  .
//  [ seven, eight, nine ]
//  [ seven, eight, ten ]
//  [ seven, nine, ten ]
//  [ eight, nine, ten ]
//  Found 120 combinations of size 3 without repetitions from a set of 10 elements.
//..
}

void next_mapping_ex() {
    std::cout << "\nExamplifying next_mapping."
              << "\n--------------------------" << std::endl;

// Enumerating all the permutations with repetition of a given size:
//------------------------------------------------------------------
// Given a set '{ 0, 1, . . . n -1 }' of size 'n', we wish to enumerate all the
// permutations of size 'r' that possibly have repetitions.  (Note that 'r' and
// 'n' can be in any relation, larger or smaller.)  We know before-hand
// that there are 'n^r' such permutations.  Each permutation with repetition is
// simply an assignment of r variables 'x[0] . . . x[r]' into the set '{ 0, 1,
// . . . n -1 }'.  Enumerating them is easy using the 'next_mapping'
// algorithm:
//..
    const int r = 5;
    const int n = 3;

    std::vector<int> v_int(r, 0);

    int N = 0;
    do {
        ++N;
        if (N < 13 || N > 237) {
            std::cout << "[ " << v_int[0];
            for (int j = 1; j < r; ++j) { std::cout << ", " << v_int[j]; }
            std::cout << " ]" << std::endl;
        } else if (N == 13) {
            std::cout << "  . . ." << std::endl;
        }
    } while (next_mapping(v_int.begin(), v_int.end(), 0, n));
    std::cout << "Found " << N << " mappings from " << n
              << " positions to a set of " << r << " elements." << std::endl;
//..
// This code will print out:
//..
//  [ 0, 0, 0, 0, 0 ]
//  [ 0, 0, 0, 0, 1 ]
//  [ 0, 0, 0, 0, 2 ]
//  [ 0, 0, 0, 1, 0 ]
//  [ 0, 0, 0, 1, 1 ]
//  [ 0, 0, 0, 1, 2 ]
//  [ 0, 0, 0, 2, 0 ]
//  [ 0, 0, 0, 2, 1 ]
//  [ 0, 0, 0, 2, 2 ]
//  [ 0, 0, 1, 0, 0 ]
//  [ 0, 0, 1, 0, 1 ]
//  [ 0, 0, 1, 0, 2 ]
//    .  .  .  .  .
//  [ 2, 2, 2, 1, 1 ]
//  [ 2, 2, 2, 1, 2 ]
//  [ 2, 2, 2, 2, 0 ]
//  [ 2, 2, 2, 2, 1 ]
//  [ 2, 2, 2, 2, 2 ]
//  Found 243 mappings from 5 positions to a set of 3 elements.
//..
// Note that this exactly enumerates the coordinates of a point in a
// 'r'-dimensional cubical grid whose side has length 'n'.  Also note that there
// isn't any special treatment for the range values, they are simply
// consecutive values in the sense that one goes from one value to the next by
// using 'operator++'.  Note that 'first_value' is *not* necessarily an iterator,
// because there is no requirement on a dereferencing 'operator*'.  However, an
// iterator *can* be used.  Note that the values pointed to by these iterators,
// or their orderings, are irrelevant.  We demonstrate this here using instead
// of the range '[0, r)' a range '[w.begin(), w.end())' into some vector of fruits.
    const char *strings[] = {
        "banana", "peach", "apple"
    };
    std::vector<std::string> W(strings, strings + n);
    const std::vector<std::string>& w = W;
       
    std::vector<std::vector<std::string>::const_iterator> v_iter(r, w.begin());

    N = 0;  // note: r and n are still 5 and 3, respectively
    do {
        ++N;
        if (N < 13 || N > 237) {
            std::cout << "[ " << *v_iter[0];
            for (int j = 1; j < r; ++j) { std::cout << ", " << *v_iter[j]; }
            std::cout << "  ]" << std::endl;
        } else if (N == 13) {
            std::cout << "  . . ." << std::endl;
        }
    } while (next_mapping(v_iter.begin(), v_iter.end(), w.begin(), w.end()));
    std::cout << "Found " << N << " mappings from " << n
              << " positions to a set of " << r << " fruits." << std::endl;
//..
//  [ banana, banana, banana, banana, banana ]
//  [ banana, banana, banana, banana, peach ]
//  [ banana, banana, banana, banana, apple ]
//  [ banana, banana, banana, peach, banana ]
//  [ banana, banana, banana, peach, peach ]
//  [ banana, banana, banana, peach, apple ]
//  [ banana, banana, banana, apple, banana ]
//  [ banana, banana, banana, apple, peach ]
//  [ banana, banana, banana, apple, apple ]
//  [ banana, banana, peach, banana, banana ]
//  [ banana, banana, peach, banana, peach ]
//  [ banana, banana, peach, banana, apple ]
//    .  .  .  .  .
//  [ apple, apple, apple, peach, peach ]
//  [ apple, apple, apple, peach, apple ]
//  [ apple, apple, apple, apple, banana ]
//  [ apple, apple, apple, apple, peach ]
//  [ apple, apple, apple, apple, apple ]
//  Found 243 mappings from 5 positions to a set of 3 fruits.
}

void next_combination_counts_ex() {
    std::cout << "\nExamplifying next_combination_counts(first, last)."
              << "\n--------------------------------------------------" << std::endl;

// Enumeration all the combinations of a given size:
//--------------------------------------------------
// Given a set '{ 0, 1, . . . n -1 }', we wish to enumerate all the
// combinations of size 'r' of elements in the set, taken with repetitions.
// This is easy using the 'next_combination' algorithm that takes only two
// arguments.  Instead of copying (possibly multiple repetitions of) elements
// into a range, we simply require a range holding the multiplicities of each
// instance in the original set.  The lexicographically first assignment of
// multiplicities with a total multiplicity of size r is '{ 0, . . . 0, r }'.
//..
    const int r = 5;
    const int n = 3;
    
    std::vector<int> multiplicities(n, 0);
    multiplicities.back() = r;
    
    int N = 0;
    do {
        ++N;
        std::cout << "[ " << multiplicities[0];
        for (int j = 1; j < n; ++j) { std::cout << ", " << multiplicities[j]; }
        std::cout << "  ]" << std::endl;
    } while (next_combination_counts(multiplicities.begin(), multiplicities.end()));
    std::cout << "Found " << N << " combinations of size " << r
              << " with repetitions from a set of " << n << " elements." << std::endl;
//..
// This code will print out:
//..
//  [ 0, 0, 5 ]
//  [ 0, 1, 4 ]
//  [ 0, 2, 3 ]
//  [ 0, 3, 2 ]
//  [ 0, 4, 0 ]
//  [ 0, 5, 0 ]
//  [ 1, 0, 4 ]
//  [ 1, 1, 3 ]
//  [ 1, 2, 2 ]
//  [ 1, 3, 1 ]
//  [ 1, 4, 0 ]
//  [ 2, 0, 3 ]
//  [ 2, 1, 2 ]
//  [ 2, 2, 1 ]
//  [ 2, 3, 0 ]
//  [ 3, 0, 2 ]
//  [ 3, 1, 1 ]
//  [ 3, 2, 0 ]
//  [ 4, 0, 1 ]
//  [ 4, 1, 0 ]
//  [ 5, 0, 0 ]
//  Found 21 combinations.
//..
// Note that it isn't hard to actually display the sequence itself.  Given a
// value of multiplicities, e.g., '{ 1, 3, 1 }', we can copy into a container
// 'w' the combination with repetition of a vector 'v'.
//..
    const char *strings[] = {
        "banana", "peach", "apple"
    };
    std::vector<std::string> V(strings, strings + n);
    const std::vector<std::string>& v = V;
       
    multiplicities[0] = 1; 
    multiplicities[1] = 3; 
    multiplicities[2] = 1; 
    assert(r == multiplicities[0] + multiplicities[1] + multiplicities[2]);

    std::vector<std::string> w;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < multiplicities[i]; ++j) {
            w.push_back(v[i]);
        }
    }
    assert(r == w.size());
//..
// Printing the container holding the repeated values:
//..
    std::cout << "Printing banana/peach/apple with multiplicities [1, 3, 1]." << std::endl;
    std::cout << "[ " << w[0];
    for (int j = 1; j < r; ++j) { std::cout << ", " << w[j]; }
    std::cout << "  ]" << std::endl;
//..
// produces:
//..
//  [ banana, peach, peach, peach, apple ]
//..
}

int main( int argc, char* argv[] )
{
    next_partial_permutation_ex();
    next_combination_ex();
    next_mapping_ex();
    next_combination_counts_ex();
}