Permutations

These functions are found in the #include <algorithm> library.

Suppose you want to go through all possible permutations of the numbers 1, 2 and 3. This requires you to go through

    1, 2, 3
    1, 3, 2
    2, 1, 3
    2, 3, 1
    3, 1, 2
    3, 2, 1

and there are $3! = 6$ permutations.

If there are duplicate entries, permutations should not show the same permutation twice. For example, given 1, 2 and 2, we want

    1, 2, 2
    2, 1, 2
    2, 2, 1

and there are $3!/2! = 3$ permutations.

Finally, given 1, 1, 2, 2, we want

    1, 1, 2, 2
    1, 2, 1, 2
    1, 2, 2, 1
    2, 1, 1, 2
    2, 1, 2, 1
    2, 2, 1, 1

and there are $4!/(2! 2!) = 6$ permutations.

The standard library allows tools for iterating through all possible permutations, and it uses the same ordering as you would find in a dictionary, so abc comes first, and cba comes last.

Thus, you can start with any range within a container that has a bi-directional iterator (which includes containers with random-access containers) and where the entries can be compared (so given two entries $x$ and $y$, either $x < y$, $x = y$ or $x > y$). In this case, the first permutation is the range sorted, and the last permutation is the range sorted in reverse order.

Given a range of entries, the function std::next_permutation( itr_first, itr_beyond ) either permutes the entries to go to the next sequence in lexicographical order and returns true, or returns false if the range is reverse sorted. Thus, the code

    std::vector<int> v{ 5, 3, 2, 6, 5 };

    do { 
        // code using the permutation
    } while ( std::next_permutation( v.begin(), v.end() ) );

would go through the permutations

     5 3 2 6 5
     5 3 5 2 6
     5 3 5 6 2
     5 3 6 2 5
     5 3 6 5 2
         .
         .
         .
     6 5 5 3 2

To start from the first permutation:

    std::vector<int> v{ 5, 3, 2, 6, 5 };
    std::sort( v.begin(), v.end() );
    // Now 'v' is 2, 3, 5, 5, 6

    do { 
        // code using the permutation
    } while ( std::next_permutation( v.begin(), v.end() ) );

and now the loop will pass through all possible permutations:

     2 3 5 5 6
         .
         .
         .
     6 5 5 3 2

The function std::prev_permutation(...) is similar, except it goes to the previous permutations, returning false if the range is sorted.

The function std::is_permutation( itr1_first, itr1_beyond, itr2_first ) determines if the entries in the range itr1_first ending at itr1_beyond are a permutation of the same number of entries starting at itr2_first.

You can view examples at replit.com.