fork download
copy 
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <map>
  4. #include <set>
  5. #include <vector>
  6.  
  7. template <typename Iterator>
  8. inline bool next_combination(const Iterator first, Iterator k, const Iterator last)
  9. {
  10.     /* Credits: Thomas Draper */
  11.     if ((first == last) || (first == k) || (last == k))
  12.         return false;
  13.     Iterator itr1 = first;
  14.     Iterator itr2 = last;
  15.     ++itr1;
  16.     if (last == itr1)
  17.         return false;
  18.     itr1 = last;
  19.     --itr1;
  20.     itr1 = k;
  21.     --itr2;
  22.     while (first != itr1)
  23.     {
  24.         if (*--itr1 < *itr2)
  25.         {
  26.             Iterator j = k;
  27.             while (!(*itr1 < *j)) ++j;
  28.             std::iter_swap(itr1, j);
  29.             ++itr1;
  30.             ++j;
  31.             itr2 = k;
  32.             std::rotate(itr1, j, last);
  33.             while (last != j)
  34.             {
  35.                 ++j;
  36.                 ++itr2;
  37.             }
  38.             std::rotate(k, itr2, last);
  39.             return true;
  40.         }
  41.     }
  42.     std::rotate(first, k, last);
  43.     return false;
  44. }
  45.  
  46.  
  47.  
  48. int main()
  49. {
  50.     std::vector<std::vector<int>> data =
  51.     {
  52.         {1, 2, 3, 4, 5},
  53.         {1, 3, 4, 5},
  54.         {1, 2, 3, 5},
  55.         {1, 3}
  56.     };
  57.     std::map<std::set<int>, int> counts;
  58.  
  59.     for (std::size_t Lsize = 1; Lsize <= 4; ++Lsize)
  60.     {
  61.         for (unsigned i = 0; i < data.size(); ++i)
  62.         {
  63.             std::size_t k = std::min(Lsize, data[i].size());
  64.  
  65.             do
  66.             {
  67.                 std::set<int> n_k(data[i].begin(), data[i].begin() + k);
  68.                 ++counts[n_k];
  69.             }
  70.             while (next_combination(data[i].begin(), data[i].begin() + k, data[i].end()));
  71.         }
  72.     }
  73.  
  74.     for (const auto& p : counts)
  75.     {
  76.         std::cout << "{";
  77.         for (auto e : p.first) {
  78.             std::cout << e << " ";
  79.         }
  80.         std::cout << "} = " << p.second << std::endl;
  81.     }
  82.  
  83.     return 0;
  84. }
  85.  
Success #stdin #stdout 0s 3436KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
{1 } = 4
{1 2 } = 2
{1 2 3 } = 2
{1 2 3 4 } = 1
{1 2 3 5 } = 2
{1 2 4 } = 1
{1 2 4 5 } = 1
{1 2 5 } = 2
{1 3 } = 6
{1 3 4 } = 2
{1 3 4 5 } = 2
{1 3 5 } = 3
{1 4 } = 2
{1 4 5 } = 2
{1 5 } = 3
{2 } = 2
{2 3 } = 2
{2 3 4 } = 1
{2 3 4 5 } = 1
{2 3 5 } = 2
{2 4 } = 1
{2 4 5 } = 1
{2 5 } = 2
{3 } = 4
{3 4 } = 2
{3 4 5 } = 2
{3 5 } = 3
{4 } = 2
{4 5 } = 2
{5 } = 3
https://ideone.com/5EPuGd
language:
C++14 (gcc 8.3)
created:
11 years 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!