使用 std::next_permutation 重复排列 'not changing the order of repetition items' with/without
Permutation with repetition 'not changing the order of repetition items' with/without using 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 在不改变重复项 with/without 顺序的情况下实现排列？
e.g.
[0] 0 1 2 2'
[1] 1 0 2 2'
[2] 1 2 0 2'
[3] 1 2 2' 0
...
next_permuation 的 reference implementation 找到数组最右边的倒序部分。如果那部分是整个数组，这就是词法上最大的排列和排列停止。如果不是，它会找到大于第一个未排序项目的最右边的项目。这些项目被交换，最右边的部分被反转。
交换项目和反转列表是“跨越”项目并失去排列稳定性的好机会。
稳定掉期
使该算法稳定的一种方法是执行“稳定交换”。假设我们有这个列表：
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;
}
}
这个算法效率不是很高。但是，大型集合的排列是不寻常的。这个 varant 的优点是它开箱即用：如果你有一个可以进行 <、== 和 != 比较的 class，你就很好。
（应该有一个变体，您将 less-than 比较器函数作为第三个参数传递。您必须将 a == b 替换为 !(a < b) && !(a > b) 并将 a != b 替换为 a < b || a > b 我想这会起作用。）
我写了一个 short demo，它有一个围绕字符串的包装器结构，其中对第一个字符进行比较。
置换和更正
如果您需要更高的效率，我认为更好的方法是首先使用常规的 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 returns 来自每个 const Stuff& 项的 int 键，它将用于排序以及插入到无序映射中。 Permuter 保留原始数组的副本。该副本首先进行稳定性排序，然后为每个键存储指向一系列相同元素的第一个元素的迭代器。排列后，该映射用于以原始顺序覆盖容器中的元素。
我写了一个 short demo 字符串，它的键是第一个字母，所以这个例子就像上面那个。
性能
一些快速但不科学的测量显示了有趣的结果：稳定的交换比不保持稳定的 std::next_permutation 只慢一点，大约 10%。 Permuter 慢得多，最多需要两倍的时间。
我预计这是相反的，但很容易看出为什么 Permuter 很慢：对于每次排列后的额外校正传递，它会复制（并因此创建）一个新的无序地图并在通过后将其撕下。那一定很浪费。 （将原始迭代器和当前迭代器成对存储在地图中没有帮助。可能有更好的方法，但我不知道如何在没有地图的情况下保持这种方法的通用性。）
稳定的交换也可能受益于良好的局部性：它不需要任何额外的数据，所有访问都只对原始数组。
从这个角度来看，我对稳定的交换非常满意。它的实现不是很复杂，在客户端代码中的用法类似于std::next_permutation。
我们在这里可以做的是使用索引，而不是值。
我们会对索引进行排列，只输出符合要求的排列。
如果我们看保持顺序的要求，那么这个就比较简单了。
让我们看看“0、1、2、2”。它在（基于零的）索引 2 和 3 处有一个重复数字。如果我们现在对 4 个索引进行排列，那么我们可以检查是否满足要求。
为此，在对索引进行排列后，我们将查找重复项的原始索引。
示例：如果排列为“0,1,3,2”，我们知道原始重复项位于 2 和 3。因此，我们查找索引 2 和 3，现在将在以下位置找到这些数字新索引 3 和 2。我们不想显示这个。
为了实现，我们将在 std::vector 中存储重复数字的索引。我们将此向量与 std::unordered_map
中重复项的值相关联
再举个例子：
一开始这样做之后，我们在std::unordered_map中有以下数据：
Value Vector with positions
0 0
1 1
2 2,3
现在，如果我们遍历所有排列，我们将搜索双精度值的原始索引。因此，我们将在索引排列中搜索 2 和 3 并找到新位置。它们也将存储在 std::vector
中
幸运的是，std::vector 有比较运算符，所以我们可以简单地比较原来的 std::vector，现在可能包含“3,2”。这将违反要求。
这当然也适用于更多组重复值。
使用上述方法的一种可能实现方式是：
#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()));
}
这对于大向量来说会很慢。也许我能想到一个数学解决方案。 . .
我曾经使用 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 在不改变重复项 with/without 顺序的情况下实现排列？
e.g.
[0] 0 1 2 2'
[1] 1 0 2 2'
[2] 1 2 0 2'
[3] 1 2 2' 0
...
next_permuation 的 reference implementation 找到数组最右边的倒序部分。如果那部分是整个数组，这就是词法上最大的排列和排列停止。如果不是，它会找到大于第一个未排序项目的最右边的项目。这些项目被交换，最右边的部分被反转。
交换项目和反转列表是“跨越”项目并失去排列稳定性的好机会。
稳定掉期
使该算法稳定的一种方法是执行“稳定交换”。假设我们有这个列表：
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;
}
}
这个算法效率不是很高。但是，大型集合的排列是不寻常的。这个 varant 的优点是它开箱即用：如果你有一个可以进行 <、== 和 != 比较的 class，你就很好。
（应该有一个变体，您将 less-than 比较器函数作为第三个参数传递。您必须将 a == b 替换为 !(a < b) && !(a > b) 并将 a != b 替换为 a < b || a > b 我想这会起作用。）
我写了一个 short demo，它有一个围绕字符串的包装器结构，其中对第一个字符进行比较。
置换和更正
如果您需要更高的效率，我认为更好的方法是首先使用常规的 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 returns 来自每个 const Stuff& 项的 int 键，它将用于排序以及插入到无序映射中。 Permuter 保留原始数组的副本。该副本首先进行稳定性排序，然后为每个键存储指向一系列相同元素的第一个元素的迭代器。排列后，该映射用于以原始顺序覆盖容器中的元素。
我写了一个 short demo 字符串，它的键是第一个字母，所以这个例子就像上面那个。
性能
一些快速但不科学的测量显示了有趣的结果：稳定的交换比不保持稳定的 std::next_permutation 只慢一点，大约 10%。 Permuter 慢得多，最多需要两倍的时间。
我预计这是相反的，但很容易看出为什么 Permuter 很慢：对于每次排列后的额外校正传递，它会复制（并因此创建）一个新的无序地图并在通过后将其撕下。那一定很浪费。 （将原始迭代器和当前迭代器成对存储在地图中没有帮助。可能有更好的方法，但我不知道如何在没有地图的情况下保持这种方法的通用性。）
稳定的交换也可能受益于良好的局部性：它不需要任何额外的数据，所有访问都只对原始数组。
从这个角度来看，我对稳定的交换非常满意。它的实现不是很复杂，在客户端代码中的用法类似于std::next_permutation。
我们在这里可以做的是使用索引，而不是值。
我们会对索引进行排列，只输出符合要求的排列。
如果我们看保持顺序的要求，那么这个就比较简单了。
让我们看看“0、1、2、2”。它在（基于零的）索引 2 和 3 处有一个重复数字。如果我们现在对 4 个索引进行排列，那么我们可以检查是否满足要求。
为此，在对索引进行排列后，我们将查找重复项的原始索引。
示例：如果排列为“0,1,3,2”，我们知道原始重复项位于 2 和 3。因此，我们查找索引 2 和 3，现在将在以下位置找到这些数字新索引 3 和 2。我们不想显示这个。
为了实现，我们将在 std::vector 中存储重复数字的索引。我们将此向量与 std::unordered_map
再举个例子：
一开始这样做之后，我们在std::unordered_map中有以下数据：
Value Vector with positions
0 0
1 1
2 2,3
现在，如果我们遍历所有排列，我们将搜索双精度值的原始索引。因此，我们将在索引排列中搜索 2 和 3 并找到新位置。它们也将存储在 std::vector
幸运的是，std::vector 有比较运算符，所以我们可以简单地比较原来的 std::vector，现在可能包含“3,2”。这将违反要求。
这当然也适用于更多组重复值。
使用上述方法的一种可能实现方式是：
#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()));
}
这对于大向量来说会很慢。也许我能想到一个数学解决方案。 . .