std::next_permutation Implementation Explanation

The std::next_permutation algorithm calculates the next lexicographically larger permutation of a given sequence. Understanding its implementation is crucial for understanding its behavior.

Algorithm Outline

The algorithm iterates over the sequence from right to left, searching for the leftmost "ascender" (i.e., an element that is smaller than its successor). If no ascender is found, it means the sequence is in decreasing order, in which case it reverses the sequence to obtain the smallest permutation.

Otherwise, the algorithm continues by finding the smallest element in the sequence to the right of the ascender (called "k"). This element is then swapped with the ascender. Finally, the elements to the right of the ascender are reversed to maintain decreasing order.

Variable Roles

• i: Points to the current element being examined.
• j: Points to the element immediately before i.
• k: Points to the smallest element in the sequence to the right of i when i is an ascender.

Loop Flow

The loop iterates until i reaches the beginning of the sequence (begin). Within each iteration:

1. If i is not an ascender, it decrements i and j.
2. If i is an ascender, it finds the smallest element to the right of i (k), swaps it with i, and reverses everything to the right of i.

Example

Consider the sequence {1, 2, 4, 3}.

• Iteration 1: i is initially at 3. j is at 2. Since 3
• Iteration 2: k is found to be 2. 3 is swapped with 2. {1, 3, 4, 2}. The elements to the right of 3 (4 and 2) are reversed. {1, 3, 2, 4}.
• Iteration 3: i is decremented and j is decremented. i is now at 2. j is at 1. 2
• Iteration 4: k is found to be 1. 2 is swapped with 1. {1, 2, 4, 3}. The elements to the right of 2 (4 and 3) are reversed. {1, 2, 3, 4}.
• Iteration 5: i is decremented and j is decremented. i is now at 1. j is at the beginning of the sequence. Since there are no more ascenders, the sequence is reversed. {4, 3, 2, 1}.