fork download
copy 
  1. // @file permutation.003.cpp
  2. // @ingroup experimental
  3. // Generate successive k-length permutations from sequence.
  4. // @note Alternate iteration; size_t version.
  5. // @date 10/25/2025
  6.  
  7. #include <algorithm>
  8. #include <vector>
  9. #include <iostream>
  10. #include <cassert>
  11.  
  12. template<typename T>
  13. struct Permutation {
  14.     typedef std::vector<T> result_type;
  15.  
  16.     template<typename InputIt>
  17.     Permutation(InputIt, InputIt, size_t k);
  18.     bool done() const;
  19.     result_type next();
  20.  
  21. private:
  22.     void m_next_permutation();
  23.  
  24.     std::vector<T>      m_items;
  25.     std::vector<size_t> m_cycle;
  26.     bool                m_done;
  27. };
  28.  
  29. template<typename T>
  30. template<typename InputIt>
  31. Permutation<T>::Permutation(InputIt first, InputIt last, size_t k)
  32. : m_items(first, last), m_done(k > m_items.size())
  33. {
  34.     if (this->done())
  35.         return;
  36.     for (size_t i = 0; i < k; i++)
  37.         m_cycle.push_back(i);
  38. }
  39.  
  40. template<typename T>
  41. bool Permutation<T>::done() const
  42. {
  43.     return m_done;
  44. }
  45.  
  46. template<typename T>
  47. auto Permutation<T>::next() -> result_type
  48. {
  49.     assert(!this->done());
  50.     auto first = m_items.begin();
  51.     result_type result(first, std::next(first, m_cycle.size()));
  52.     m_next_permutation();
  53.     return result;
  54. }
  55.  
  56. template<typename T>
  57. void Permutation<T>::m_next_permutation()
  58. {
  59.     size_t n = m_items.size();
  60.     size_t k = m_cycle.size();
  61.  
  62.     for (size_t i = k-1; i != static_cast<size_t>(-1); i--)
  63.     {
  64.         if (++m_cycle[i] < n)
  65.         {
  66.             std::swap(m_items[i], m_items[m_cycle[i]]);
  67.             return;
  68.         }
  69.         m_cycle[i] = i;
  70.         auto first = std::next(m_items.begin(), i);
  71.         std::rotate(first, std::next(first, 1), m_items.end());
  72.     }
  73.     m_done = true;
  74. }
  75.  
  76. template<typename InputIt>
  77. auto make_permutation(InputIt first, InputIt last, size_t k)
  78. {
  79.     typedef typename std::iterator_traits<InputIt>::value_type value_type;
  80.     return Permutation<value_type>(first, last, k);
  81. }
  82.  
  83. template<typename InputIt>
  84. auto make_permutation(InputIt first, InputIt last)
  85. {
  86.     return make_permutation(first, last, std::distance(first, last));
  87. }
  88.  
  89. //
  90. // Main.
  91. //
  92.  
  93. template<typename T>
  94. void show(Permutation<T>&& permutation)
  95. {
  96.     while (!permutation.done())
  97.     {
  98.         for (auto x : permutation.next())
  99.             std::cout << x;
  100.         std::cout << ' ';
  101.     }
  102.     std::cout << std::endl;
  103. }
  104.  
  105. int main()
  106. {
  107.     // Expect: AB AC AD BA BC BD CA CB CD DA DB DC
  108.     std::string s{"ABCD"};
  109.     show(make_permutation(s.begin(), s.end(), 2));
  110.  
  111.     // Expect: 012 021 102 120 201 210
  112.     std::vector<int> v{0, 1, 2};
  113.     show(make_permutation(v.begin(), v.end()));
  114. }
Success #stdin #stdout 0s 5324KB
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/msPGey
language:
C++ (gcc 8.3)
created:
7 days 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!