#include <iostream>
#include <algorithm>
#include <vector>
#include <unordered_map>

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;
};

/*
 *      A wrapper around a string that compares the first letter only
 */
struct Stringlet {
    std::string str;
};

std::ostream& operator<<(std::ostream& os, const Stringlet& s)
{
    os << s.str;
    return os;
}

template<class T>
void put(std::ostream& os, T first, T last)
{
    size_t n = 0;
    os << "[";
    
    while (first < last) {
        if (n++) os << ", ";
        os << *first++;
    }
    
    os << "]\n";
}

int skey(const Stringlet& s)
{
    return s.str[0];
}

int main(void)
{
    Stringlet orig[] = {
        "1", "11", "111",
        "2", "22", "222"
    };
    size_t n = 6;

    std::vector<Stringlet> pool;
    
    for (size_t i = 0; i < n; i++) {
        pool.push_back(orig[i]);
    }
    
    Permuter<std::vector<Stringlet>::iterator, int> perm(pool.begin(),
        pool.end(), skey); 
    
    do {
        put(std::cout, pool.begin(), pool.end());
    } while (perm.next());

    return 0;
}