Partition [N] elements into [K] non-empty subsets

N_Into_K_Subsets



Program for partitioning N elements into non-empty subsets of size K.

#include<iostream>
#include<vector>

using namespace std;

int subset_count = 0;

// Function for partitioning n elements into k non-empty subsets.
void Generate_Subsets (int element, int n, int k, int non_empty_subsets, 
                       vector<vector<int>>& subsets) {
    
    if (element > n) { // Max available number in a set is n.
        if (non_empty_subsets == k) { // We have generted k non-empty subsets.
            cout << "---------------" << endl;
            subset_count++;
            cout << "Subset : " << subset_count << endl;
            for (auto& set : subsets) {
                for(auto& num : set) {
                    cout << num << " ";
                } cout << endl;
            }
        }
        return;
    }

    for (int i=0; i<subsets.size(); i++) {
        if (subsets[i].size() > 0) {
            subsets[i].push_back(element);
            Generate_Subsets(element+1, n, k, non_empty_subsets, subsets);
            subsets[i].pop_back();
        } else { // empty subset
            subsets[i].push_back(element);
            Generate_Subsets(element+1, n, k, non_empty_subsets+1, subsets);
            subsets[i].pop_back();
            break;
        }
    }
}

int main() {
    int n = 4; // Given N elements. ( 1..n )
    int k = 3; // To be partitioned into k subsets.
    vector<vector<int>> subsets(k);
    cout << "N: " << n << " K: " << k << endl;
    Generate_Subsets(1, n, k, 0, subsets); // Start by pushing the 1'st element

    k = 2;
    subset_count = 0;
    vector<vector<int>> subsets_1(k);   
    cout << "===================================" << endl;
    cout << "N : " << n << " K: " << k << endl;
    Generate_Subsets(1, n, k, 0, subsets_1); // Start by pushing the 1'st element
    return 0;
}

Output

N: 4 K: 3
---------------
Subset : 1
1 2 
3 
4 
---------------
Subset : 2
1 3 
2 
4 
---------------
Subset : 3
1 
2 3 
4 
---------------
Subset : 4
1 4 
2 
3 
---------------
Subset : 5
1 
2 4 
3 
---------------
Subset : 6
1 
2 
3 4 
===================================
N: 4 K: 2
---------------
Subset : 1
1 2 3 
4 
---------------
Subset : 2
1 2 4 
3 
---------------
Subset : 3
1 2 
3 4 
---------------
Subset : 4
1 3 4 
2 
---------------
Subset : 5
1 3 
2 4 
---------------
Subset : 6
1 4 
2 3 
---------------
Subset : 7
1 
2 3 4 



Copyright (c) 2019-2022, Algotree.org.
All rights reserved.