使用/不使用 std::next_permutation 进行重复排列“不改变重复项的顺序”

Question

我曾经使用 来实现重复排列std::next_permutation。

但我发现 it( std::next_permutation) 改变了重复项目的位置。

e.g.
[0] 0 1 2 2'
[1] 2' 0 1 2
[2] 2' 1 0 2
[3] 2' 1 2 0 
...

如何使用重复实现排列而不改变重复项的顺序（使用/不使用）std::next_permutation？

e.g.
[0] 0 1 2 2'
[1] 1 0 2 2'
[2] 1 2 0 2'
[3] 1 2 2' 0
...

Answer 1

的参考实现查找next_permuation倒序数组的最右边部分。如果该部分是整个数组，则这是词法上最大的排列和排列停止点。如果不是，它会找到大于第一个未排序项目的最右边的项目。这些项目被交换并且最右边的部分被颠倒。

\n

交换项目和反转列表是“跨越”项目并失去排列稳定性的绝佳机会。

\n

稳定的互换

\n

使该算法稳定的一种方法是执行“稳定交换”。假设我们有这个列表：

\n

1  1\' 1" 2  2\'\n

\n

我们想交换最外面的项目。交换后的列表应该是：

\n

2  1  1\' 2\' 1"\n

\n

我们可以通过进行两次循环交换来实现这一点。我们拿起1，朝 移动2\'，每当我们看到另一个，我们就放置原来的1并采取1\'等等。2\'对于向冒泡也是如此1。

\n

这种稳定的交换可能如下所示：

\n

namespace stable {\n    template<class T>\n    void iter_swap(T a, T b)\n    {\n        T lo = std::min(a, b);\n        T hi = std::max(a, b);\n\n        if (*lo != *hi) {\n            auto loval = *lo;\n            auto hival = *hi;\n\n            for (auto it = lo + 1; it < hi; ++it) {\n                if (loval == *it) {\n                    std::swap(loval, *it);\n                }\n            }\n\n            for (auto it = hi; it-- > lo; ) {\n                if (hival == *it) {\n                    std::swap(hival, *it);\n                }\n            }\n\n            *lo = hival;\n            *hi = loval;\n        }\n    }\n}\n

\n

当然，现在交换是 O(N) 操作，而不是通常的 O(1) 操作。对于反向操作来说更糟糕，我使用了简单的实现 \xe2\x80\x93 我想还有一些改进的空间：

\n

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

\n

现在，在原始next_permutation算法中使用这两个稳定变体：

\n

namespace stable {\n    template<class T>\n    bool next_permutation(T first, T last)\n    {\n        auto r_first = std::make_reverse_iterator(last);\n        auto r_last = std::make_reverse_iterator(first);\n        auto left = std::is_sorted_until(r_first, r_last);\n\n        if (left != r_last){\n            auto right = std::upper_bound(r_first, left, *left);\n            stable::iter_swap(left, right);\n        }\n\n        stable::reverse(left.base(), last);\n\n        return left != r_last;\n    }\n}\n

\n

该算法效率不是很高。但是，大型集合的排列是不寻常的。这个变体的优点是它可以开箱即用：如果您有一个可以执行<、==和!=比较的类，那么您就很好了。

\n

（应该有一个变体，您可以将小于比较器函数作为第三个参数传递。我猜，您必须替换a == b为!(a < b) && !(a > b)和a != bwitha < b || a > b才能使其工作。）

\n

我编写了一个简短的演示，其中有一个字符串周围的包装结构，其中对第一个字符进行比较。

\n

排列并修正

\n

如果您需要更高的效率，我认为更好的方法是std::next_permutation首先使用常规，然后通过以正确的顺序用相同元素覆盖每个出现的元素，在第二遍中“拉直”排列数组。

\n

这样做需要设置一些额外的数据。也许每组相同元素应该有一个唯一的、可比较的和可散列的键，可用于比较和将原始元素存储在映射中。

\n

这是这个想法的实现：

\n

template<class Iter, typename Key>\nclass Permuter {\npublic:\n    Permuter(Iter begin_, Iter end_,\n        Key (*key_)(const typename Iter::value_type& ref))\n    : begin(begin_), end(end_), key(key_), less(Less(key_))\n    {\n        Iter it = begin_;\n        \n        while (it != end_) {\n            orig.push_back(*it++);\n        }\n        \n        std::stable_sort(orig.begin(), orig.end(), less);\n        \n        typename std::vector<typename Iter::value_type>::iterator vec;\n        vec = orig.begin();\n        \n        while (vec != orig.end()) {\n            Key k = key(*vec);\n\n            if (map.find(k) == map.end()) {\n                map.insert(std::make_pair(k, vec));\n            }\n            \n            vec++;\n        }        \n    }\n    \n    bool next()\n    {\n        if (std::next_permutation(begin, end, less)) {\n            auto mmap = map;\n            auto it = begin;\n            \n            while (it != end) {\n                *it = *mmap[key(*it)]++;\n                it++;\n            }\n\n            return true;\n        }\n        \n        return false;\n    }\n\nprivate:\n    struct Less {\n        Key (*key)(const typename Iter::value_type& iter);\n\n        Less(Key (*key_)(const typename Iter::value_type& iter))\n        : key(key_) {}\n\n        bool operator()(const typename Iter::value_type& a,\n                      const typename Iter::value_type& b)\n        {\n            return (key(a) < key(b));\n        }\n    };\n\n    Iter begin;\n    Iter end;\n    Key (*key)(const typename Iter::value_type& iter);\n    std::vector<typename Iter::value_type> orig;\n    std::unordered_map<Key,\n        typename std::vector<typename Iter::value_type>::iterator > map;\n    Less less;\n};\n

\n

这个想法是，您创建一个实例，permuter它是现有双向可迭代集合的包装器，然后调用该next方法：

\n

Permuter<std::vector<Stuff>::iterator, int>\n    perm(stuff.begin(), stuff.end(), stuff_key); \n\ndo {\n    // so something with std::vector<Stuff> stuff\n} while (perm.next());\n

\n

这里，该函数从每个项目stuff_key返回一个键，该键将用于排序以及插入到无序映射中。保留原始数组的副本。首先对该副本进行稳定性排序，然后为每个键存储指向一系列相同元素的第一个元素的迭代器。排列后，该映射用于按原始顺序覆盖容器中的元素。intconst Stuff&Permuter

\n

我已经编写了一个简短的演示，其键是第一个字母的字符串，因此示例与上面的示例类似。

\n

表现

\n

一些快速但不科学的测量显示了有趣的结果：稳定的交换结果只比std::next_permutation不保持稳定性的交换慢一点，大约 10%。速度Permuter要慢得多，需要花费两倍的时间。

\n

我预计这是相反的情况，但很容易看出为什么速度Permuter很慢：对于每次排列后的额外校正过程，它会制作一个副本（并因此创建）一个新的无序映射，并在之后将其撕毁通行证。那一定很浪费。（将原始迭代器和当前迭代器作为对存储在映射中没有帮助。可能有更好的方法，但我不知道如何在没有映射的情况下保持这种方法的通用性。）

\n

稳定的交换还可能受益于良好的局部性：它不需要任何额外的数据，并且所有访问仅针对原始数组。

\n

从这个角度来看，我对稳定的交换感到非常满意。std::next_permutation它的实现并不是很复杂，就像在客户端代码中一样使用。

\n