#include <algorithm>
#include <iostream>
#include <map>
#include <set>
#include <vector>

template <typename Iterator>
inline bool next_combination(const Iterator first, Iterator k, const Iterator last)
{
    /* Credits: Thomas Draper */
    if ((first == last) || (first == k) || (last == k))
        return false;
    Iterator itr1 = first;
    Iterator itr2 = last;
    ++itr1;
    if (last == itr1)
        return false;
    itr1 = last;
    --itr1;
    itr1 = k;
    --itr2;
    while (first != itr1)
    {
        if (*--itr1 < *itr2)
        {
            Iterator j = k;
            while (!(*itr1 < *j)) ++j;
            std::iter_swap(itr1, j);
            ++itr1;
            ++j;
            itr2 = k;
            std::rotate(itr1, j, last);
            while (last != j)
            {
                ++j;
                ++itr2;
            }
            std::rotate(k, itr2, last);
            return true;
        }
    }
    std::rotate(first, k, last);
    return false;
}



int main()
{
    std::vector<std::vector<int>> data =
    {
        {1, 2, 3, 4, 5},
        {1, 3, 4, 5},
        {1, 2, 3, 5},
        {1, 3}
    };
    std::map<std::set<int>, int> counts;

    for (std::size_t Lsize = 1; Lsize <= 4; ++Lsize)
    {
        for (unsigned i = 0; i < data.size(); ++i)
        {
            std::size_t k = std::min(Lsize, data[i].size());

            do
            {
                std::set<int> n_k(data[i].begin(), data[i].begin() + k);
                ++counts[n_k];
            }
            while (next_combination(data[i].begin(), data[i].begin() + k, data[i].end()));
        }
    }

    for (const auto& p : counts)
    {
        std::cout << "{";
        for (auto e : p.first) {
            std::cout << e << " ";
        }
        std::cout << "} = " << p.second << std::endl;
    }

    return 0;
}