fork download 
  1.  
  2. #include <iostream>
  3. #include <algorithm>
  4. #include <vector>
  5.  
  6. namespace stable {
  7.     template<class T>
  8.     void iter_swap(T a, T b)
  9.     {
  10.         T lo = std::min(a, b);
  11.         T hi = std::max(a, b);
  12.  
  13.         if (*lo != *hi) {
  14.             auto loval = *lo;
  15.             auto hival = *hi;
  16.  
  17.             for (auto it = lo + 1; it < hi; ++it) {
  18.                 if (loval == *it) {
  19.                     std::swap(loval, *it);
  20.                 }
  21.             }
  22.  
  23.             for (auto it = hi; it-- > lo; ) {
  24.                 if (hival == *it) {
  25.                     std::swap(hival, *it);
  26.                 }
  27.             }
  28.  
  29.             *lo = hival;
  30.             *hi = loval;
  31.         }
  32.     }
  33.  
  34.     template<class T>
  35.     void reverse(T first, T last)
  36.     {
  37.         while (first != last && first != --last) {
  38.             stable::iter_swap(first++, last);
  39.         }
  40.     }
  41.  
  42.  
  43.     template<class T>
  44.     bool next_permutation(T first, T last)
  45.     {
  46.         auto r_first = std::make_reverse_iterator(last);
  47.         auto r_last = std::make_reverse_iterator(first);
  48.         auto left = std::is_sorted_until(r_first, r_last);
  49.  
  50.         if (left != r_last){
  51.             auto right = std::upper_bound(r_first, left, *left);
  52.             stable::iter_swap(left, right);
  53.         }
  54.  
  55.         stable::reverse(left.base(), last);
  56.  
  57.         return left != r_last;
  58.     }
  59. }
  60.  
  61. /*
  62.  *      A wrapper around a string that compares the first letter only
  63.  */
  64. struct Stringlet {
  65.     std::string str;
  66.  
  67.     bool operator <(const Stringlet& other) const
  68.     {
  69.         return (str[0] < other.str[0]);
  70.     }
  71.  
  72.     bool operator ==(const Stringlet& other) const
  73.     {
  74.         return (str[0] == other.str[0]);
  75.     }
  76.  
  77.     bool operator !=(const Stringlet& other) const
  78.     {
  79.         return (str[0] != other.str[0]);
  80.     }
  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 main(void)
  104. {
  105.     Stringlet orig[] = {"1 ", "11", "2 ", "22", "2\"", "3 "};
  106.     size_t n = 4;
  107.  
  108.     std::vector<Stringlet> pool;
  109.  
  110.     for (size_t i = 0; i < n; i++) {
  111.         pool.push_back(orig[i]);
  112.     }
  113.  
  114.     do {
  115.         put(std::cout, pool.begin(), pool.end());
  116.     } while (stable::next_permutation(pool.begin(), pool.end()));
  117.  
  118.     return 0;
  119. }
  120.  
Success #stdin #stdout 0.01s 5356KB
comments (?)
stdin 
Standard input is empty
stdout 
[1 , 11, 2 , 22]
[1 , 2 , 11, 22]
[1 , 2 , 22, 11]
[2 , 1 , 11, 22]
[2 , 1 , 22, 11]
[2 , 22, 1 , 11]
https://ideone.com/rN3gw7
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!