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