Multiset Partitioning Problem

In mathematics, a partition of a set is a grouping of its elements into non-empty subsets, in such a way that the number of elements in the original set always equals the sum of the number of elements in each partition.

Equivalently, a family of sets P is a partition of X if and only if all of the following conditions hold:

  • The family P does not contain the empty set
  • The union of the sets in P is equal to X. The sets in P are said to cover X.
  • The intersection of any two distinct sets in P is empty i.e. the elements of P are said to be pairwise disjoint.

The number of possible partitions of a set of n elements is B(n) known as the Bell number. As we know, this problem is NP-Complete i.e. it has a non-polynomial time solution.

Solving for a smaller set in Polynomial time

But for a smaller set, we could try to find a way to generate all partitions.
Let’s take an example, given a collection of numbers that may contain duplicates, find all partitions of it. (all possible ways of dividing the collection.) For a set i.e. when each element in a multiset has multiplicity 1, there’s a nice solution here. But it doesn’t solve the problem when there are duplicate elements present in the set.

Also read: Bitmasking

Let the multiset be {1, 1, 2}, it has 4 partitions:
partition 1 = { {1}, {1}, {2} }
partition 2 = { {1}, {1, 2} }
partition 3 = { {1, 1}, {2} }
partition 4 = { {1, 1, 2} }

Here’s a brute-force solution for a set with/without duplicates using backtracking and recursion

Code Implementation

//
//  main.cpp
//  Multiset Partitioning Problem
//
//  Created by Himanshu on 11/01/23.
//

#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;

void solve (set<vector<vector<int>>>& solution, vector<int> inputSet,
            vector<vector<int>>& partitions, vector<int> partition,
            int n, int i) {
    
    int numberOfElements = 0;
    for (int i=0; i<partitions.size(); i++) {
        numberOfElements += partitions[i].size();
    }
    
    if (numberOfElements == n) {
        vector<vector<int>> newPartitions = partitions;
        for (int i=0; i<newPartitions.size(); i++) {
            sort (newPartitions[i].begin(), newPartitions[i].end());
        }
        sort(newPartitions.begin(), newPartitions.end());
        solution.insert(newPartitions);
        return;
    }
    
    for (int j=i; j<n; j++) {
        partition.push_back(inputSet[j]);
        partitions.push_back(partition);
        vector<int> partitionNew;
        solve(solution, inputSet, partitions, partitionNew, n, j+1);
        partitions.pop_back();
    }
}

void permute (set<vector<vector<int>>>& solution, vector<int>& inputSet,
              int i, int n) {
    
    if (i == n) {
        vector<int> partition;
        vector<vector<int>> partitions;
        solve(solution, inputSet, partitions, partition, (int) inputSet.size(), 0);
        return;
    }
    
    for (int j=i; j<=n; j++) {
        swap(inputSet[i], inputSet[j]);
        permute(solution, inputSet, i+1, n);
        swap(inputSet[i], inputSet[j]);
    }
}

int main() {
    vector<int> inputSet {1, 1, 2, 3}, partition;
    set<vector<vector<int>>> partitions;
    set<vector<vector<int>>>::iterator it;
    
    permute(partitions, inputSet, 0, (int) inputSet.size()-1);
    
    int counter = 1;
    for (it = partitions.begin(); it!=partitions.end(); it++) {
        cout<<"Partitions set "<<counter++<<":"<<endl;
        for (int i = 0; i<(*it).size(); i++) {
            for(int j = 0; j<(*it)[i].size(); j++) {
                cout<<(*it)[i][j]<<" ";
            }
            cout<<endl;
        }
    }
    
    return 0;
}

Output

Partitions set 1:
1 
1 
2 
3 
Partitions set 2:
1 
1 
2 3 
Partitions set 3:
1 
1 2 
3 
Partitions set 4:
1 
1 2 3 
Partitions set 5:
1 
1 3 
2 
Partitions set 6:
1 1 
2 
3 
Partitions set 7:
1 1 
2 3 
Partitions set 8:
1 1 2 
3 
Partitions set 9:
1 1 2 3 
Partitions set 10:
1 1 3 
2 
Partitions set 11:
1 2 
1 3 

Here’s the working example: Generate all Partitions

Leave a Reply

Your email address will not be published. Required fields are marked *