fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. template <typename IT>
  6. bool next_partial_permutation(IT beg, IT mid, IT end) {
  7.     if (beg == mid) { return false; }
  8.     if (mid == end) { return std::next_permutation(beg, end); }
  9.  
  10.     auto p1 = mid;
  11.  
  12.     while (p1 != end && !(*(mid - 1) < *p1))
  13.         ++p1;
  14.  
  15.     if (p1 != end) {
  16.         std::swap(*p1, *(mid - 1));
  17.         return true;
  18.     } else {
  19.         std::reverse(mid, end);
  20.         auto p3 = std::make_reverse_iterator(mid);
  21.  
  22.         while (p3 != std::make_reverse_iterator(beg) && !(*p3 < *(p3 - 1)))
  23.             ++p3;
  24.  
  25.         if (p3 == std::make_reverse_iterator(beg)) {
  26.             std::reverse(beg, end);
  27.             return false;
  28.         }
  29.  
  30.         auto p2 = end - 1;
  31.  
  32.         while (!(*p3 < *p2))
  33.             --p2;
  34.  
  35.         std::swap(*p3, *p2);
  36.         std::reverse(p3.base(), end);
  37.         return true;
  38.     }
  39. }
  40.  
  41. int main() {
  42.     std::vector<int> z = {1, 1, 2, 3, 4, 4};
  43.     int m = 3;
  44.     int n = z.size();
  45.  
  46.     do {
  47.         for (int j = 0; j < m; ++j)
  48.             std::cout << z[j] << ' ';
  49.  
  50.         std::cout << std::endl;
  51.     } while (next_partial_permutation(z.begin(), z.begin() + m, z.end()));
  52.  
  53.     for (int j = 0; j < n; ++j)
  54.         std::cout << z[j] << ' ';
  55.  
  56.     std::cout << std::endl;
  57. }
  58.  
Success #stdin #stdout 0s 4520KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1 1 2 
1 1 3 
1 1 4 
1 2 1 
1 2 3 
1 2 4 
1 3 1 
1 3 2 
1 3 4 
1 4 1 
1 4 2 
1 4 3 
1 4 4 
2 1 1 
2 1 3 
2 1 4 
2 3 1 
2 3 4 
2 4 1 
2 4 3 
2 4 4 
3 1 1 
3 1 2 
3 1 4 
3 2 1 
3 2 4 
3 4 1 
3 4 2 
3 4 4 
4 1 1 
4 1 2 
4 1 3 
4 1 4 
4 2 1 
4 2 3 
4 2 4 
4 3 1 
4 3 2 
4 3 4 
4 4 1 
4 4 2 
4 4 3 
1 1 2 3 4 4
https://ideone.com/Ya7oeU
language:
C++ (gcc 8.3)
created:
4 years ago
visibility:
public

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!