使用/不使用std::next_permutation的重复置换“不改变重复项的顺序”
我曾经用std::next_permutation实现重复置换。
但是我发现它(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
...Stack Overflow用户
发布于 2022-04-14 14:54:46
参考实施 for next_permuation查找数组的最右边部分，并按相反顺序排列。这部分是整个数组，这是词汇上最大的排列和排列停止。如果没有，则会找到比第一个未排序项更大的最右边项。这些物品被交换，最右边的部分被反转。
交换项目和反转列表是“跳跃”于项目之上并失去排列稳定性的好机会。
稳定互换
使该算法稳定的一种方法是执行“稳定交换”。所以说我们有一份清单：
1 1' 1" 2 2'我们要交换最外面的东西。交换后的列表应该是：
2 1 1' 2' 1"我们可以通过做两个循环互换来实现这一点。我们使用1，移动到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;
}
}
}当然，现在交换操作是O(N)操作，而不是通常的O(1)操作。相反的操作就更糟糕了，我已经使用了简单的实现--我想还有一些改进的余地：
namespace stable {
template<class T>
void reverse(T first, T last)
{
while (first != last && first != --last) {
stable::iter_swap(first++, last);
}
}
}现在，在原始next_permutation算法中使用这两个稳定的变体：
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;
}
}这种算法效率不高。但是，大型收藏品上的排列是不寻常的。这个变体的优点是它可以开箱即用:如果您有一个类可以进行<、==和!=比较，那么您就很好了。
(应该有一个变体，将小于比较器函数作为第三个参数传递。我想，你必须用!(a < b) && !(a > b)代替a == b，用a < b || a > b代替a != b，这样才能起作用。)
我编写了一个短演示，它在字符串周围有一个包装器结构，对第一个字符进行比较。
不变与正确
如果您需要更好的效率，我认为更好的方法是首先使用常规的std::next_permutation，然后再用相同的元素以正确的顺序覆盖每个发生的元素，从而在第二次传递中“纠正”置换数组。
这样做需要设置一些额外的数据。也许，对于每组相同的元素，应该有一个独特的、可比较的和可使用的键，这些元素可以用于比较和在地图中存储原始元素。
下面是这个想法的一个实现：
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实例，该实例是现有双向迭代集合的包装器，然后调用next方法：
Permuter<std::vector<Stuff>::iterator, int>
perm(stuff.begin(), stuff.end(), stuff_key);
do {
// so something with std::vector<Stuff> stuff
} while (perm.next());在这里，函数stuff_key从每个const Stuff&项返回一个int键，该键将用于排序和插入无序映射。Permuter保存原始数组的副本。该副本首先按照稳定性排序，然后为每个键存储到一系列相同元素的第一个元素的迭代器。置换后，该映射用于用原始顺序覆盖容器中的元素。
我编写了一个带有字符串的短演示，该字符串的键是第一个字母，因此示例类似于上面的示例。
性能
一些快速和不科学的测量结果显示了有趣的结果:稳定掉期的速度比没有保持稳定的std::next_permutation慢一些，大约10%。Permuter的速度要慢得多，花费的时间是原来的两倍。
我原以为情况正好相反，但很容易看出为什么Permuter速度慢:对于每次排列后附加的校正传递，它会复制(因此创建)一个新的无序地图，并在传递后将其撕下来。那一定是浪费。(将原始迭代器和当前迭代器存储为映射中的对没有帮助。也许有更好的方法，但我看不出如何在没有地图的情况下保持这种方法的通用性。)
稳定的交换也可能受益于良好的局部性:它不需要任何额外的数据，而且所有的访问都只访问原始数组。
从这个角度来看，我对稳定的交换很满意。它的实现不是很复杂，它在客户端代码中的使用类似于std::next_permutation。
https://stackoverflow.com/questions/71871064
复制相似问题
腾讯云开发者
