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

Question

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.

Sordino

One of the sets in each partition contains zero, one, or two 1's, and zero or one 2's. The remaining smaller set can then be partitioned recursively. – Intercession

@Intercession can you write the code? – Sordino

By the way, there is not a unique definition of "partition of a multiset" because there are four possibilities: partition into a set of sets; a set of multisets; a multiset of sets; or a multiset of multisets. Your example suggests you are looking for the last one but since all four partition types have their uses, it would be better to be clear. – Oceanic

Answer 1

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.

Conservatoire

Answer 2

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.

Isis

The set to be partitioned is a multiset, or bag. The concept of power sets can be extended to multisets but the size of the multipowerset is not a power of two; rather, it is the product of one more than the cardinality of each unique element. (If all elements are unique, which is the case for a set, then that formula reduces to two to the power of the number of elements. But the size of the multipowerset of, for example, {1, 1, 1, 2, 3, 3} is 4*2*3 = 24. (Also, powersets are only incidentally useful for enumerating partitions.) – Oceanic

@Oceanic , well said. This feels very similar to finding all factors given the prime factorization. Maybe I’m thinking of multiplicative partitions? – Leban

@joseph: yes, that's a related problem. Every factor is an element of the multipowerset of the prime factorization, but that only helps a little in finding the set of multiplicative partitions. – Oceanic

The question is not looking for all the subsets of S. It's looking for all ways of dividing the collection of numbers. So, in the example, there are 4 ways, each line being a solution. – Sordino

There are 11 ways to partition {1, 1, 2, 3}. Your output only shows 8. – Oceanic

Now it works with that simple input, but I tried it with input {1, 1, 1, 2, 3, 3, 3} and it produced 125 partitions, although there are only 109. I didn't examine the output carefully, but observed that partition 102 ({1 2} {1 3} {1 3 3}) is the same as partition 104 ({1 2} {1 3 3} {1 3}). Presumably there are other such duplicates. – Oceanic

... I guess the bug is your cmp function, which is unnecessary and incorrect. std::vector already has an operator<, and your version (1) only looks at two elements even if one or both vectors have more, and (2) always looks at two elements, even if one or both vectors have less. The first just leads to a partial sort, but the second is undefined behaviour (array index out of range). I just removed it (and the reference to it) and got the correct output count for that example. – Oceanic

Yeah that was a quick code. But I intentionally had only two elements check in the comparator because it was just an example. Ofcourse, it would have failed for larger input. I didn't know that comparator was unnecessary. I will update the link. – Isis

You shouldn't paste code which you know to be erroneous, particularly code which produces Undefined Behaviour, and doubly so when you don't insert any comments. People copy and paste code from here, trustingly. You should respect that by being trustworthy. – Oceanic

It was not erroneous. It produced correct output for the asked input. Moreover I think that part was not an important part of the problem asked, but mere being a C++ syntactic issue. – Isis