#include <functional>
#include <algorithm>
#include <iostream>
#include <iterator>
#include <ostream>
#include <string>

using namespace std;

// _____________________[ recursive stable group ]___________________________ //

// stable merge of adjacent groups
template<typename BidirectionalIterator>
void merge_groups(BidirectionalIterator first,BidirectionalIterator middle,BidirectionalIterator last)
{
    typedef reverse_iterator<BidirectionalIterator> ReverseIterator;
    BidirectionalIterator i=middle,current,sub_last,next_to_same;
    while(i != last)
    {
        current = i++;
        sub_last=find(i,last,*current);
        if(sub_last!=last)
            i = sub_last;
        next_to_same = find(ReverseIterator(current),ReverseIterator(first),*current).base();
        if(next_to_same!=first)
           rotate(next_to_same,current,i);
    }
}

template<typename BidirectionalIterator>
void stable_group(BidirectionalIterator first,BidirectionalIterator last)
{
    if(first!=last)
    {
        BidirectionalIterator middle=first;
        typename iterator_traits<BidirectionalIterator>::difference_type range_size = distance(first,last);
        if(range_size>2)
        {
            advance(middle,range_size/2);
            stable_group(first,middle);
            stable_group(middle,last);
            merge_groups(first,middle,last);
        }
    }
}

// __________________________________________________________________________ //

template<typename BidirectionalIterator>
void group_gold(BidirectionalIterator first,BidirectionalIterator last)
{
    typedef typename iterator_traits<BidirectionalIterator>::value_type value_type;
    while(first!=last)
        first = stable_partition(first, last, bind1st(equal_to<value_type>(),*first));
}

template<typename Range>
void test_with_gold(const Range &s)
{
    Range p = s;
    do
    {
        next_permutation(begin(p),end(p));
        auto gold = p, recursive = p;
        group_gold(begin(gold),end(gold));
        stable_group(begin(recursive),end(recursive));
        if(gold!=recursive)
        {
            cout << "Error, gold and recursive result differs" << endl;
            cout << "Gold=" << gold << endl;
            cout << "Recursive=" << recursive << endl;
        }
    }while(p!=s);
}

int main()
{
    string tests[] =
    {
        "vvabcbbcc",
        "asdfrrafdsr",
        "abcdefgijkl",
        "010101010101",
        "totobobolol"
    };
    for(auto &&s : tests)
    {
        test_with_gold(s);
        stable_group(begin(s),end(s));
        cout << s << endl;
    }
}