fork(1) download 
  1. // Generate successive k-length permutations from sequence. (1.00)
  2. // (algorithm adapted from python/itertools page)
  3.  
  4. #include <algorithm>
  5. #include <vector>
  6. #include <iostream>
  7.  
  8. template<typename T>
  9. struct Permutation {
  10.     template<typename InputIt>
  11.     Permutation(InputIt, InputIt, int k);
  12.     bool next();
  13.     std::vector<T> get() const;
  14.  
  15. private:
  16.     std::vector<T>   m_pool;
  17.     std::vector<int> m_index;
  18.     std::vector<int> m_cycle;
  19. };
  20.  
  21. template<typename T>
  22. template<typename InputIt>
  23. Permutation<T>::Permutation(InputIt first, InputIt last, int k)
  24. : m_pool(first, last)
  25. {
  26.     int n = m_pool.size();
  27.     for (int i = 0; i < n; i++)
  28.         m_index.push_back(i);
  29.     k = std::min(k, n);
  30.     for (int i = 0; i < k; i++)
  31.         m_cycle.push_back(n-i);
  32. }
  33.  
  34. template<typename T>
  35. bool Permutation<T>::next()
  36. {
  37.     int n = m_pool.size();
  38.     for (int k = m_cycle.size(), i = k-1; i >= 0; i--)
  39.     {
  40.         if (--m_cycle[i])
  41.         {
  42.             std::swap(m_index[i], m_index[n - m_cycle[i]]);
  43.             return true;
  44.         }
  45.         m_cycle[i] = n - i;
  46.         auto first = m_index.begin();
  47.         std::rotate(std::next(first, i), std::next(first, i+1), m_index.end());
  48.     }
  49.     return false;
  50. }
  51.  
  52. template<typename T>
  53. std::vector<T> Permutation<T>::get() const
  54. {
  55.     std::vector<T> out;
  56.     for (int k = m_cycle.size(), i = 0; i < k; i++)
  57.         out.push_back(m_pool[m_index[i]]);
  58.     return out;
  59. }
  60.  
  61. template<typename InputIt>
  62. auto make_permutation(InputIt first, InputIt last, int k)
  63. {
  64.     typedef typename std::iterator_traits<InputIt>::value_type value_type;
  65.     return Permutation<value_type>(first, last, k);
  66. }
  67.  
  68. template<typename InputIt>
  69. auto make_permutation(InputIt first, InputIt last)
  70. {
  71.     return make_permutation(first, last, std::distance(first, last));
  72. }
  73.  
  74. //
  75. // Main.
  76. //
  77.  
  78. template<typename T>
  79. void show(Permutation<T>&& permutation)
  80. {
  81.     do
  82.     {
  83.         for (auto x : permutation.get())
  84.             std::cout << x;
  85.         std::cout << ' ';
  86.     }
  87.     while (permutation.next());
  88.     std::cout << std::endl;
  89. }
  90.  
  91. int main()
  92. {
  93.     // Expect: AB AC AD BA BC BD CA CB CD DA DB DC
  94.     std::string s{"ABCD"};
  95.     show(make_permutation(s.begin(), s.end(), 2));
  96.  
  97.     // Expect: 012 021 102 120 201 210
  98.     std::vector<int> v{0, 1, 2};
  99.     show(make_permutation(v.begin(), v.end()));
  100. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin 
Standard input is empty
stdout 
AB AC AD BA BC BD CA CB CD DA DB DC 
012 021 102 120 201 210
https://ideone.com/hHkYMq
language:
C++ (gcc 8.3)
created:
1 day 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!