fork(1) download
copy 
  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
copy 
Standard input is empty
stdout
copy 
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!