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.