fork download 
  1.  
  2. #include <iostream>
  3. #include <algorithm>
  4. #include <vector>
  5. #include <unordered_map>
  6.  
  7. template<class Iter, typename Key>
  8. class Permuter {
  9. public:
  10.     Permuter(Iter begin_, Iter end_,
  11.         Key (*key_)(const typename Iter::value_type& ref))
  12.     : begin(begin_), end(end_), key(key_), less(Less(key_))
  13.     {
  14.         Iter it = begin_;
  15.  
  16.         while (it != end_) {
  17.             orig.push_back(*it++);
  18.         }
  19.  
  20.         std::stable_sort(orig.begin(), orig.end(), less);
  21.  
  22.         typename std::vector<typename Iter::value_type>::iterator vec;
  23.         vec = orig.begin();
  24.  
  25.         while (vec != orig.end()) {
  26.             Key k = key(*vec);
  27.  
  28.             if (map.find(k) == map.end()) {
  29.                 map.insert(std::make_pair(k, vec));
  30.             }
  31.  
  32.             vec++;
  33.         }        
  34.     }
  35.  
  36.     bool next()
  37.     {
  38.         if (std::next_permutation(begin, end, less)) {
  39.             auto mmap = map;
  40.             auto it = begin;
  41.  
  42.             while (it != end) {
  43.                 *it = *mmap[key(*it)]++;
  44.                 it++;
  45.             }
  46.  
  47.             return true;
  48.         }
  49.  
  50.         return false;
  51.     }
  52.  
  53. private:
  54.     struct Less {
  55.         Key (*key)(const typename Iter::value_type& iter);
  56.  
  57.         Less(Key (*key_)(const typename Iter::value_type& iter))
  58.         : key(key_) {}
  59.  
  60.         bool operator()(const typename Iter::value_type& a,
  61.                       const typename Iter::value_type& b)
  62.         {
  63.             return (key(a) < key(b));
  64.         }
  65.     };
  66.  
  67.     Iter begin;
  68.     Iter end;
  69.     Key (*key)(const typename Iter::value_type& iter);
  70.     std::vector<typename Iter::value_type> orig;
  71.     std::unordered_map<Key,
  72.         typename std::vector<typename Iter::value_type>::iterator > map;
  73.     Less less;
  74. };
  75.  
  76. /*
  77.  *      A wrapper around a string that compares the first letter only
  78.  */
  79. struct Stringlet {
  80.     std::string str;
  81. };
  82.  
  83. std::ostream& operator<<(std::ostream& os, const Stringlet& s)
  84. {
  85.     os << s.str;
  86.     return os;
  87. }
  88.  
  89. template<class T>
  90. void put(std::ostream& os, T first, T last)
  91. {
  92.     size_t n = 0;
  93.     os << "[";
  94.  
  95.     while (first < last) {
  96.         if (n++) os << ", ";
  97.         os << *first++;
  98.     }
  99.  
  100.     os << "]\n";
  101. }
  102.  
  103. int skey(const Stringlet& s)
  104. {
  105.     return s.str[0];
  106. }
  107.  
  108. int main(void)
  109. {
  110.     Stringlet orig[] = {
  111.         "1", "11", "111",
  112.         "2", "22", "222"
  113.     };
  114.     size_t n = 6;
  115.  
  116.     std::vector<Stringlet> pool;
  117.  
  118.     for (size_t i = 0; i < n; i++) {
  119.         pool.push_back(orig[i]);
  120.     }
  121.  
  122.     Permuter<std::vector<Stringlet>::iterator, int> perm(pool.begin(),
  123.         pool.end(), skey); 
  124.  
  125.     do {
  126.         put(std::cout, pool.begin(), pool.end());
  127.     } while (perm.next());
  128.  
  129.     return 0;
  130. }
Success #stdin #stdout 0.01s 5576KB
comments (?)
stdin 
Standard input is empty
stdout 
[1, 11, 111, 2, 22, 222]
[1, 11, 2, 111, 22, 222]
[1, 11, 2, 22, 111, 222]
[1, 11, 2, 22, 222, 111]
[1, 2, 11, 111, 22, 222]
[1, 2, 11, 22, 111, 222]
[1, 2, 11, 22, 222, 111]
[1, 2, 22, 11, 111, 222]
[1, 2, 22, 11, 222, 111]
[1, 2, 22, 222, 11, 111]
[2, 1, 11, 111, 22, 222]
[2, 1, 11, 22, 111, 222]
[2, 1, 11, 22, 222, 111]
[2, 1, 22, 11, 111, 222]
[2, 1, 22, 11, 222, 111]
[2, 1, 22, 222, 11, 111]
[2, 22, 1, 11, 111, 222]
[2, 22, 1, 11, 222, 111]
[2, 22, 1, 222, 11, 111]
[2, 22, 222, 1, 11, 111]
https://ideone.com/bo6TC2
language:
C++ (gcc 8.3)
created:
3 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!