CODEWITHSUNDEEP
algorithmsetcombinationspartitioning
Alex
Alex

Reputation: 2976

How to find all partitions of a multiset (a set that allows duplicates)

Given a collection of numbers that may contain duplicates, find all partitions of it. (all possible ways of dividing the collection.)

For instance, the multiset {1, 1, 2} has 4 partitions:

partition 1 = { {1}, {1}, {2} } partition 2 = { {1}, {1, 2} } partition 3 = { {1, 1}, {2} } partition 4 = { {1, 1, 2} }

Here is a similar question How to find all partitions of a set but in that question, all numbers are distinct.

Definition for set partitions: https://en.wikipedia.org/wiki/Partition_of_a_set

Definition for multiset： https://en.wikipedia.org/wiki/Multiset

A solution written in any common programming language with some explanation will be greatly appreciated.

Update：

Seems like a lot of people are confused what the question is asking about. It's NOT asking for all the possible subsets of the given collection. Rather, it's asking you to find out all the different ways of dividing the given collection of numbers.

Upvotes: 6

Views: 1410

Answers (2)

lrnv
lrnv

Reputation: 1106

Hey I do have a python solution:

from sympy.utilities.iterables import multiset_partitions

for pi in multiset_partitions([1,1,3]):
    print(pi)

Looking at the code, you can find the algorithm in Knuth's AOCP

Algorithm M, page 39-40.

The AOCP is also described here

Refer to Volume 3b, Algorithm M, page 39-40.

Upvotes: 4

Himanshu Kansal
Himanshu Kansal

Reputation: 570

It's a Partition set problem.

Number of elements in the original set always equals to the sum of number of elements in each partition.

It can be solved using backtracking and recursion. This C++ program might be useful.

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, 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]);
    }
}

Here's the working example: Generate all Partitions

EDIT: I misread the question. I have updated the answer. It now generates all possible partitions.

Upvotes: -3

Related Questions