Counting subsets with given sizes of a set

Question

Given a set C with n elements (duplicates allowed) and a partition P of n
P = {i1, i2, ... / i1+i2+... = n} how many different decompositions of C in subsets of size i1, i2, ... are there ?

Example :

C = {2 2 2 3}

P = {2 2}
C = {2 2} U {2 3}

P = {1 1 2}
C = {2} U {2} U {2 3}
C = {2} U {3} U {2 2}

P = {1 3}
C = {2} U {2 2 3}
C = {3} U {2 2 2}

I have a solution, but it is inefficient when C has more than a dozen of elements.
Thanks in advance
Philippe

Answer 1

The fact that the order of decomposition does not matter to you makes it much harder. That is, you are viewing {2 2} U {2 3} as the same as {2 3} U {2 2}. Still I have an algorithm that is better than what you have, but is not great.

Let me start it with a realistically complicated example. Our set will be A B C D E F F F F G G G G. The partition will be 1 1 1 1 2 2 5.

My first simplification will be to represent the information we care about in the set with the data structure [[2, 4], [5, 1]], meaning 2 elements are repeated 4 times, and 5 are repeated once.

My second apparent complication will be to represent the partition with [[5, 1, 1], [2, 2, 1], [4, 1, 1]. The pattern may not be obvious. Each entry is of the form [size, count, frequency]. So the one distinct instance of 2 partitions of size 2 turn into [2, 2, 1]. We're not using frequency yet, but it is counting distinguishable piles of the same size and commonness.

Now we're going to recurse as follows. We'll take the most common element, and find all of the ways to use it up. So in our case we take one of the piles of size 4, and find that we can divide it as follows, rearranging each remaining partition strategy in lexicographic order:

1. [4] leaving [[1, 1, 1], [2, 2, 1], [1, 4, 1]] = [[2, 2, 1], [1, 4, 1], [1, 1, 1]].
2. [3, [1, 0], 0] leaving [[2, 1, 1], [1, 1, 1], [2, 1, 1], [1, 4, 1]] = [[2, 1, 2], [1, 4, 1], [1, 1, 1]. (Note that we're now using frequency.)
3. [3, 0, 1] leaving [[2, 1, 1], [2, 2, 1], [0, 1, 1], [1, 3, 1]] = [[2, 2, 1], [2, 1, 1], [1, 3, 1]]
4. [2, [2, 0], 0] leaving [[3, 1, 1], [0, 1, 1], [2, 1, 1], [1, 4, 1]] = [[3, 1, 1], [2, 1, 1], [1, 4, 1]]
5. [2, [1, 1], 0] leaving [[3, 1, 1], [1, 2, 1], [1, 4, 1]] = [[3, 1, 1], [1, 4, 1], [1, 2, 1]]
6. [2, [1, 0], [1]] leaving [[3, 1, 1], [1, 1, 1], [2, 1, 1], [0, 1, 1], [1, 3, 1]] = [[3, 1, 1], [2, 1, 1], [1, 4, 1], [1, 1, 1]]
7. [2, 0, [1, 1]] leaving `[[3, 1, 1], [2, 2, 1], [0, 2, 1], [1, 2, 1]] = [[3, 1, 1], [2, 2, 1], [1, 2, 1]]1
8. [1, [2, 1]] leaving [[4, 1, 1], [0, 1, 1], [1, 1, 1], [1, 4, 1]] = [[4, 1, 1], [1, 4, 1], [1, 1, 1]]
9. [1, [2, 0], [1]] leaving [[4, 1, 1], [0, 1, 1], [2, 1, 1], [0, 1, 1], [1, 3, 1]] = [[4, 1, 1], [2, 1, 1], [1, 3, 1]]
10. [1, [1, 0], [1, 1]] leaving [[4, 1, 1], [1, 1, 1], [2, 1, 1], [0, 2, 1], [1, 2, 1]] = [[4, 1, 1], [2, 1, 1], [1, 2, 1], [1, 1, 1]]
11. [1, 0, [1, 1, 1]] leaving [[4, 1, 1], [2, 2, 1], [0, 3, 1], [1, 1, 1]] = [[4, 1, 1], [2, 2, 1], [1, 1, 1]]
12. [0, [2, 2]] leaving [[5, 1, 1], [0, 2, 1], [1, 4, 1]] = [[5, 1, 1], [1, 4, 1]]
13. [0, [2, 1], [1]] leaving [[5, 1, 1], [0, 1, 1], [1, 1, 1], [0, 1, 1], [1, 3, 1]] = [[5, 1, 1], [1, 3, 1], [1, 1, 1]]
14. [0, [2, 0], [1, 1]] leaving [[5, 1, 1], [0, 2, 1], [2, 1, 1], [0, 2, 1], [1, 2, 1]] = [[5, 1, 1], [2, 1, 1], [1, 2, 1]]
15. [0, [1, 1], [1, 1]] leaving [[5, 1, 1], [1, 2, 1], [0, 2, 1], [1, 2, 1]] = [[5, 1, 1,], [1, 2, 2]]
16. [0, [1, 0], [1, 1, 1]] leaving [[5, 1, 1], [1, 1, 1], [2, 1, 1], [0, 3, 1], [1, 1, 1]] = [[5, 1, 1], [2, 1, 1], [1, 1, 2]]
17. [0, 0, [1, 1, 1, 1]] leaving [[5, 1, 1], [2, 2, 1], [0, 4, 1]] = [[5, 1, 1], [2, 2, 1]]

Now each of those subproblems can be solved recursively. This may feel like we're on the way to constructing them all, but we aren't, because we memoize the recursive steps. It turns out that there are a lot of ways that the first two groups of 8 can wind up with the same 5 left overs. With memoization we don't need to repeatedly recalculate those solutions.

That said, we'll do better. Groups of 12 elements should not pose a problem. But we're not doing that much better. I wouldn't be surprised if it starts breaking down somewhere around groups of 30 or so elements with interesting sets of partitions. (I haven't coded it. It may be fine at 30 and break down at 50. I don't know where it will break down. But given that you're iterating over sets of partitions, at some fairly small point it will break down.)