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