问使用/不使用std::next_permutation的重复置换“不改变重复项的顺序”

EN

1  1' 1" 2  2'

2  1  1' 2' 1"

namespace stable {
    template<class T>
    void iter_swap(T a, T b)
    {
        T lo = std::min(a, b);
        T hi = std::max(a, b);

        if (*lo != *hi) {
            auto loval = *lo;
            auto hival = *hi;

            for (auto it = lo + 1; it < hi; ++it) {
                if (loval == *it) {
                    std::swap(loval, *it);
                }
            }

            for (auto it = hi; it-- > lo; ) {
                if (hival == *it) {
                    std::swap(hival, *it);
                }
            }

            *lo = hival;
            *hi = loval;
        }
    }
}

namespace stable {
    template<class T>
    void reverse(T first, T last)
    {
        while (first != last && first != --last) {
            stable::iter_swap(first++, last);
        }
    }
}

namespace stable {
    template<class T>
    bool next_permutation(T first, T last)
    {
        auto r_first = std::make_reverse_iterator(last);
        auto r_last = std::make_reverse_iterator(first);
        auto left = std::is_sorted_until(r_first, r_last);

        if (left != r_last){
            auto right = std::upper_bound(r_first, left, *left);
            stable::iter_swap(left, right);
        }

        stable::reverse(left.base(), last);

        return left != r_last;
    }
}

template<class Iter, typename Key>
class Permuter {
public:
    Permuter(Iter begin_, Iter end_,
        Key (*key_)(const typename Iter::value_type& ref))
    : begin(begin_), end(end_), key(key_), less(Less(key_))
    {
        Iter it = begin_;
        
        while (it != end_) {
            orig.push_back(*it++);
        }
        
        std::stable_sort(orig.begin(), orig.end(), less);
        
        typename std::vector<typename Iter::value_type>::iterator vec;
        vec = orig.begin();
        
        while (vec != orig.end()) {
            Key k = key(*vec);

            if (map.find(k) == map.end()) {
                map.insert(std::make_pair(k, vec));
            }
            
            vec++;
        }        
    }
    
    bool next()
    {
        if (std::next_permutation(begin, end, less)) {
            auto mmap = map;
            auto it = begin;
            
            while (it != end) {
                *it = *mmap[key(*it)]++;
                it++;
            }

            return true;
        }
        
        return false;
    }

private:
    struct Less {
        Key (*key)(const typename Iter::value_type& iter);

        Less(Key (*key_)(const typename Iter::value_type& iter))
        : key(key_) {}

        bool operator()(const typename Iter::value_type& a,
                      const typename Iter::value_type& b)
        {
            return (key(a) < key(b));
        }
    };

    Iter begin;
    Iter end;
    Key (*key)(const typename Iter::value_type& iter);
    std::vector<typename Iter::value_type> orig;
    std::unordered_map<Key,
        typename std::vector<typename Iter::value_type>::iterator > map;
    Less less;
};

Permuter<std::vector<Stuff>::iterator, int>
    perm(stuff.begin(), stuff.end(), stuff_key); 

do {
    // so something with std::vector<Stuff> stuff
} while (perm.next());

Value  Vector with positions
 0          0
 1          1
 2          2,3 

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <numeric>

int main() {
    // Test Data
    std::vector data{ 0,1,2,2 };

    // Find duplicated values and their positions
    std::unordered_map<int, std::vector<size_t>> valuesAndPositionsOriginal{};
    for (size_t index{}; index < data.size(); ++index)
        valuesAndPositionsOriginal[data[index]].push_back(index);

    // We will work and do permutations of indices
    std::vector<size_t> indices(data.size());
    std::iota(indices.begin(), indices.end(), 0);

    // Here we will store the current positions of the suplicates after a permutation
    std::vector<size_t> currentPositions{};

    do {
        // If any set of duplicates will be reversed, then we will not show it
        bool allOk{ true };

        // For this permutation, make a check of the current indeces with the original ones
        for (const auto& [value, positions] : valuesAndPositionsOriginal) {

            // Need only to do something, if there are duplicates, so if value was there more than once
            if (positions.size() > 1) {

                currentPositions.clear();
                // Where is the index from the original position now?

                for (const size_t pos : positions)
                    currentPositions.push_back(std::distance(indices.begin(), std::find(indices.begin(), indices.end(), pos)));

                // And this is the evaluation, if the positions were reversed
                if (currentPositions > positions)
                    allOk = false;
            }
        }
        // Show result
        if (allOk) {
            for (const size_t index : indices)
                std::cout << data[index] << ' ';
            std::cout << '\n';
        }

    } while (std::next_permutation(indices.begin(), indices.end()));
}