如何获取std::next_permutation执行后容器的最左变更位置？

Great question! Let's break this down step by step, starting with how std::next_permutation works under the hood—since that's where the "leftmost changed position" is hiding.

First, let's recap the core steps of the standard std::next_permutation algorithm (using 0-based indices for clarity):

• Step 1: Traverse from the end of the container backwards to find the first index i where arr[i] < arr[i+1]. If no such index exists, we're at the last permutation, and the function returns false.
• Step 2: Traverse backwards again to find the first index j where arr[j] > arr[i].
• Step 3: Swap arr[i] and arr[j].
• Step 4: Reverse the subarray from i+1 to the end of the container.

Now, think about what changes when generating the next permutation:

• All elements before i stay exactly the same (since i is the first position where the element is smaller than its right neighbor—everything to the left is in non-increasing order, so we can't get a larger permutation without modifying i).
• The element at i is swapped with a larger value, and the suffix is reversed. So the leftmost position where the new sequence differs from the original is exactly i.

That's the key insight! We don't need to compare the original and modified sequences with std::mismatch—the index i from step 1 is our answer.

We can adapt the standard algorithm to return this index instead of just a boolean. Here's a C++ implementation that works for any random-access container:

#include <algorithm>
#include <iterator>

template <typename RandomIt>
int next_permutation_with_leftmost(RandomIt first, RandomIt last) {
    if (first == last) return -1; // Empty range has no permutations
    RandomIt i = last - 1;
    if (first == i) return -1; // Single element can't be permuted

    // Step 1: Find the first i where arr[i] < arr[i+1]
    while (true) {
        RandomIt i1 = i;
        --i;
        if (*i < *i1) {
            // Step 2: Find the first j from the end where arr[j] > arr[i]
            RandomIt j = last - 1;
            while (!(*j > *i)) --j;
            // Step 3: Swap elements at i and j
            std::iter_swap(i, j);
            // Step 4: Reverse the suffix starting at i1
            std::reverse(i1, last);
            // Return 0-based index relative to the start of the container
            return std::distance(first, i);
        }
        if (i == first) {
            // No next permutation exists; reset to first permutation (standard behavior)
            std::reverse(first, last);
            return -1;
        }
    }
}

Example usage: #

#include <vector>
#include <iostream>
#include <numeric>

int main() {
    std::vector<int> arr(4);
    std::iota(arr.begin(), arr.end(), 1); // Initialize with [1,2,3,4]
    
    int pos;
    do {
        // Print current permutation
        for (int num : arr) std::cout << num << " ";
        std::cout << "\n";
        
        pos = next_permutation_with_leftmost(arr.begin(), arr.end());
        if (pos != -1) {
            std::cout << "Leftmost changed position: " << pos << "\n";
        } else {
            std::cout << "No more permutations available\n";
        }
    } while (pos != -1);
    
    return 0;
}

Sample output snippet:

1 2 3 4 
Leftmost changed position: 2
1 2 4 3 
Leftmost changed position: 1
1 3 2 4 
Leftmost changed position: 2
1 3 4 2 
...

For a fixed number of elements N, the sequence of leftmost positions is deterministic (since permutations are generated in lex order). We can generate this sequence in two ways:

Approach 1: Simulate permutations (simple, efficient for small N) #

We can initialize a permutation of 1..N and repeatedly run our custom function to collect positions:

#include <vector>
#include <numeric>

std::vector<int> get_leftmost_positions(int N) {
    std::vector<int> perm(N);
    std::iota(perm.begin(), perm.end(), 1);
    std::vector<int> positions;
    
    int pos;
    do {
        pos = next_permutation_with_leftmost(perm.begin(), perm.end());
        if (pos != -1) {
            positions.push_back(pos);
        }
    } while (pos != -1);
    
    return positions;
}

For N=3, this returns [1,0,1,0,1]—which matches manual calculation of permutation transitions.

Approach 2: Combinatorial generation (memory-efficient for larger N) #

Storing full permutations becomes impractical for N > 10 (since 10! = 3.6 million). Instead, we can model the permutation state using factorial number system logic to track the leftmost position without generating full permutations. The core idea is:

• The leftmost position k appears (N-1 -k)! * (k) times? No, more accurately:
  • Position 0 (the first element) changes (N-1) times (once after each full group of (N-1)! permutations starting with the same first element).
  • For position k (1 ≤ k ≤ N-2), its occurrence count is (N-1 -k)! multiplied by the number of times the prefix up to k-1 can be permuted.

For most use cases, the simulation approach is simpler and sufficient—factorial growth limits practical N values anyway.

内容的提问来源于stack exchange，提问作者rwst