Std::Next_Permutation Implementation Explanation

std::next_permutation Implementation Explanation

Let's look at some permutations:

How do we go from one permutation to the next? Firstly, let's look at things a little differently. We can view the elements as digits and the permutations as numbers. Viewing the problem in this way we want to order the permutations/numbers in "ascending" order.

When we order numbers we want to "increase them by the smallest amount". For example when counting we don't count 1, 2, 3, 10, ... because there are still 4, 5, ... in between and although 10 is larger than 3, there are missing numbers which can be gotten by increasing 3 by a smaller amount. In the example above we see that 1 stays as the first number for a long time as there are many reorderings of the last 3 "digits" which "increase" the permutation by a smaller amount.

So when do we finally "use" the 1? When there are only no more permutations of the last 3 digits.

And when are there no more permutations of the last 3 digits? When the last 3 digits are in descending order.

Aha! This is key to understanding the algorithm. We only change the position of a "digit" when everything to the right is in descending order because if it isn't in descending order then there are still more permutations to go (ie we can "increase" the permutation by a smaller amount).

Let's now go back to the code:

while (true)
{
    It j = i;
    --i;

    if (*i < *j)
    { // ...
    }

    if (i == begin)
    { // ...
    }
}

From the first 2 lines in the loop, j is an element and i is the element before it.
Then, if the elements are in ascending order, (if (*i < *j)) do something.

Otherwise, if the whole thing is in descending order, (if (i == begin)) then this is the last permutation.

Otherwise, we continue and we see that j and i are essentially decremented.

We now understand the if (i == begin) part so all we need to understand is the if (*i < *j) part.

Also note: "Then if the elements are in ascending order ..." which supports our previous observation that we only need to do something to a digit "when everything to the right is in descending order". The ascending order if statement is essentially finding the leftmost place where "everything to the right is in descending order".

Let's look again at some examples:

...
1 4 3 2
2 1 3 4
...
2 4 3 1
3 1 2 4
...

We see that when everything to the right of a digit is in descending order, we find the next largest digit and put it in front and then put the remaining digits in ascending order.

Let's look at the code:

It k = end;

while (!(*i < *--k))
    /* pass */;

iter_swap(i, k);
reverse(j, end);
return true;

Well, since the things to the right are in descending order, to find the "next largest digit" we just have to iterate from the end, which we see in the first 3 lines of code.

Next, we swap the "next largest digit" to the front with the iter_swap() statement and then since we know that digit was the next largest, we know that the digits to the right are still in descending order, so to put it in ascending order, we just have to reverse() it.

std::next_permutation Implementation Explanation seeming little inefficient?

You will rarely have an array you want to permute with more than 15 elements (and actually even less), because it would require you to process 15! > 10^12 different permutations. And for arrays with such a small size binary search is less efficient than simple linear search.

How to force jumps with std::next_permutation

You would have to write some custom rules for that. A smart way to do this would be to write a code, in which whenever you have a set of permutations which are not valid, you jump to the next permutation you can get which will be valid.

For eg, in the above case, knowing that 2 at 2nd position is invalid, you could write the code to swap 2 and 3, and ensure that the permutation then achieved is the smallest one possible with 3 in that location, and so on.

Also, if you were writing your own implementation of next_permuation, ensure that the internal functioning is as close to that of next_permutation. You can read about it here: std::next_permutation Implementation Explanation

Why can't I generate all permutations with std::next_permutation?

From the reference:

Permutes the range [first, last) into the next permutation, where the set of all permutations is ordered lexicographically with respect to operator< or comp.

So iterating through the permutations will only give you the lexicographically increasing sequence from the initial range.

Note that the example at the bottom of the reference page does a std::sort on the initial range in order to generate all permutations.

Python implementation for next_permutation in STL

itertools.permutations is close; the biggest difference is it treats all items as unique rather than comparing them. It also doesn't modify the sequence in-place. Implementing std::next_permutation in Python could be a good exercise for you (use indexing on a list rather than random access iterators).
No. Python iterators are comparable to input iterators, which are an STL category, but only the tip of that iceberg. You must instead use other constructs, such as a callable for an output iterator. This breaks the nice syntax generality of C++ iterators.

how to handle reappearing values with std::next_permutation

Consider the four integer values 4, 5, 5, 5. The four possible permutations are 4, 5, 5, 5 and 5, 4, 5, 5 and 5, 5, 4, 5 and 5, 5, 5, 4. That's it. The three 5s have the same value, so they cannot be distinguished from each other. The algorithm doesn't keep track of which of those values originally came before the other; they're the same. The same thing applies to present: there are three distinct values, not four.

next_permutation time complexity in big O notation

The complexity of std::next_permutation that transforms the permutation to the next permutation in the lexicographic order is O(n) in the worst case.

The number of permutations of n distinct elements is n!. The number of permutations of multisets is n!/(n1!*n2!*...*nk!) where ni is the number of equal elements of type i.

We have two different cases:

Distinct numbers (set).
next_permutation is often (if not always) implemented with O(1) amortized time when all elements are distinct. The latter means that next_permutation will have O(1) average time when calling many times consequently.
In this scenario, the complexity of your permutationSort function is O(n!) in the worst-case scenario because of n! loop iterations with the amortized O(1) call of next_permutation.
Numbers with repetitions (multiset)
In this case, next_permutation has no guaranteed O(1) amortized complexity, but the number of 'permutations of multiset' could be much less than n!. The upper bound of the permutationSort function complexity is O(n!*n) in the worst case. I suppose it can be reduced to O(n!) but don't know how to prove this fact.