Get all subsets from a set — Mechanics of software

How to extract all combinations (unordered subsets) from a given set in C++?

Let us estimate the count before. Suppose N is the size of a given set, and K is the number of elements in the subset. The count of all combinations (unordered subsets) of size K is

C(N, K) = N! / (K! * (N - K)!)

Then the count of all subsets is

C(N, 1) + C(N, 2) + ... + C(N, N) = 2^N - 1

So we expect to produce 7 subsets from a set of 3 elements, 15 subsets from 4-elements set, and so on.

#include <iostream>
#include <vector>

using set_t = std::vector<int>;
using subsets_t = std::vector<set_t>;

void make_combinations(const set_t& data, const size_t index, const set_t& current_subset, subsets_t& subsets)
{
    for (size_t i = index; i < data.size(); i++)
    {
        set_t subset = current_subset;
        subset.push_back(data[i]);
        subsets.push_back(subset);
        make_combinations(data, i + 1, subset, subsets);
    }
}

subsets_t get_subsets(const set_t& data)
{
    subsets_t subsets;
    make_combinations(data, 0, set_t(), subsets);
    return subsets;
}

void print_subsets(const subsets_t& subsets)
{
    std::cout << "Subset count: " << subsets.size() << std::endl;
    for (const auto& subset : subsets)
    {
        for (const auto value : subset)
        {
            std::cout << value << " ";
        }
        std::cout << std::endl;
    }
    std::cout << std::endl;
}

int main()
{
    subsets_t subsets = get_subsets({ 1, 2, 3, 4 });
    print_subsets(subsets);
    return 0;
}

Result

Subset count: 15
1
1 2
1 2 3
1 2 3 4
1 2 4
1 3
1 3 4
1 4
2
2 3
2 3 4
2 4
3
3 4
4

Mechanics of software Programming is thinking, not typing
Home \| Categories \| Tags \| Search	\| eng \| рус