I used to implement permutation with repetition by using std::next_permutation.
But I found that it(std::next_permutation) changes location of item which is repeated.
e.g.
[0] 0 1 2 2'
[1] 2' 0 1 2
[2] 2' 1 0 2
[3] 2' 1 2 0
...
How can I implement permutation with repetition not changing the order of repetition items with/without using 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
...
The reference implementation for next_permuation finds the rightmost portion of the array that is in reverse order. It that portion is the whole array, this is the lexically greatest permutation and permutation stops. If not, it finds the rightmost item that is greater than the first unsorted item. These items are swapped and the rightmost portion is reversed.
Swapping items and reversig the list are great opportunities to "leapfrog" over items and lose stability of the permutation.
One way to make this algorithm stable is to perform a "stable swap". So say we have this list:
1 1' 1" 2 2'
and we want to swap the outermost items. After swapping the list should be:
2 1 1' 2' 1"
We can achieve that by doing two circular swaps. We take the 1, move towards the 2' and whenever we see another one, we place the original 1 and take the 1' and so on. The same is done for bubbling up the 2' towards the 1.
This stable swap could look like this:
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;
}
}
}
Of course, now swapping is an O(N) operation instead of the usual O(1). It's even worse for the reverse operation, where I've used the naive implementation – I guess there's some room for improvement:
namespace stable {
template<class T>
void reverse(T first, T last)
{
while (first != last && first != --last) {
stable::iter_swap(first++, last);
}
}
}
Now, use these two stable variants in the original next_permutation algorithm:
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;
}
}
This algorithm isn't terribly efficient. But then, permutations on large collections are unusual. This varant has the advantage that it works out of the box: If you have a class that can do <, == and != comparisons, you're good.
(There ought to be a variant where you pass the less-than comparator function as third parameter. You must replace a == b with !(a < b) && !(a > b) and a != b with a < b || a > b for this to work, I guess.)
I've written a short demo that has a wrapper struct around a string, where comparisons are done on the first character.
If you need better efficiency, I think a better approach is to use the regular std::next_permutation first and then "straighten" the permuted array in a second pass by overwriting each occurrence of an element with an identical element in the correct order.
Doing that will require to set up some extra data. Perhaps there should be a unique, comparable and hashable key to each group of identical elements which can be used for comparison and for storing the original elements in a map.
Here's an implementation of that idea:
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;
};
The idea is that you create an instance of permuter that is a wrapper around an existing bidirectionally iterable collection and then call the next method:
Permuter<std::vector<Stuff>::iterator, int>
perm(stuff.begin(), stuff.end(), stuff_key);
do {
// so something with std::vector<Stuff> stuff
} while (perm.next());
Here the function stuff_key returns an int key from each const Stuff& item, which will be used for sorting and also for insertion into an unordered map. The Permuter keeps a copy of the original array. That copy is sorted with stability first, then an iterator to the first element of a range of identical elements is stored for each key. After permuting, that map is used to overwrite the elements in the container with their original order.
I've written a short demo with strings whose keys are the first letter, so the example is like the one above.
Some quick and unscientific measurements show interesting results: The stable swap turns out to be onle a little slower, about 10%, than the std::next_permutation that doesn't maintain stability. The Permuter is much slower, it takes up to twice as much time.
I expected this to be the other way round, but it's easy to see why the Permuter is slow: For the additional corrective pass after each permutation, it makes a copy (and therefore creates) a new unordered map and tears it down after the pass. That must be wasteful. (Storing the original and the current iterator as pair in the map disn't help. There are probably better ways, but I don't see how to keep this approach generic without the map.)
The stable swap may also benefit from good locality: It does not require any additional data and all accesses are to the original array only.
In that light, I'm quite happy with the stable swap. Its implementation is not very complicated and it is used like std::next_permutation in the client code.
What we could do here, is to work with indices, instead of values.
We would do permutations with the indices and only output the permutations that meet the requirement.
If we look at the requirement to keep the order, then this is rather simple.
Let us look at "0, 1, 2, 2". It has a repeating number at (zero based) index 2 and 3. If we do now permutations for the 4 indices, then we can check, if the requirment is met or not.
For this, after doing the permutation of the indices, we will look for the original indices for the duplicates.
Example: If the permutation is "0,1,3,2", we know that the original duplicates were at 2 and 3. So, we look up the index 2 and 3 and will find these numbers now at new indices 3 and 2. And this we do not want to show.
For the implementation, we will store the indices for duplicate numbers in a std::vector. And we associate this vector with the value for the duplicate in an std::unordered_map
Example again:
After doing this in the beginning, we have the follwing data in the std::unordered_map:
Value Vector with positions
0 0
1 1
2 2,3
Now, if we go over all permutations, we will search for the original indices for double values. So, we will search for the 2 and 3 in the permutation of the indices and find there new position. They will be stored also in a std::vector
Fortunately, the std::vector has comparison operators and so, we can simply compare the orignal std::vector which now may contain "3,2". And this would violate the requirement.
This will of course work also for more groups of repeated values.
One possible implementation using the above approach could be:
#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()));
}
This will be slow for big vectors. Maybe I can think of a mathematical solution . . .