Anyone know of a simple algorithm to systematically enumerate all the partitions of a set? (Ie all ways in which a set can be exhaustively partitioned into subsets)? Here for eg is me merely trying to count all the partitions of a set of 7. Probably some mistakes here.
Conversation
I faced this problem during my PhD and I looked into partition theory (both set and integer) ~2002 but it defeated me. So I kinda band-aided over and skipped past it.
1
1
There’s actually 2 things that go by the name partition theory. Integer partition theory is all the ways a number can be broken down into additive components. Set partition theory is all the ways to make mutually exclusive and exhaustive subsets out of a set.
1
2
They’re related of course. The integer partitions of the cardinal ity of a set help you map the cases of the set partitions, and you can then do the combinatorics to count the instances within that case which is what I’ve done above.
2
1
Some good leads in the replies, thanks. This comes up surprisingly often but it’s surprising there’s no widely used and efficient partition theory library that I know of (both integer and set).
1
1
I need minio.., I mean grad students. Solutions to this would be a key enabler for several problems that interest me. But it doesn’t directly interest me. I am pretty sure enumerating all partitions in a deterministic way is NP complete, but instances of a case might be P.
1
Related problems in case anyone wants a major yak shave:
1. Enumerating all unique ordered sequences for every component of every partition instance
2. Generalization: all DAGs on every component of every partition instance (so each partition would be a forest of DAGs)
2
Big practical use is explicitly laying out the configuration space of a multiagent system so you can solve optimal configuration problems.
Replying to
A simple example is dividing 22 soccer players into 2 teams in the most balanced way (maximizing uncertainty of outcome). Simple approximation heuristics exist for this, like pick 2 captains and have them take turns picking players. Or you divide/I pick. But general case is hard.
3
2
2
1
1
Main math thing to know is Stirling numbers of the second kind, for those interested (and related Bell numbers linked within)
2
1
2
To be clear the problem is to list them systematically, not count them
Eg for {a, b, c}
abc
a bc
ab c
ac b
a b c
2
The last time I needed this I just randomized it using balls-in-urns and my numbers were small enough I hit all of them after fairly few iterations. But this time I need to enumerate them in a deterministic order.
1
Really dislike careful deterministic programming and a big fan of randomized methods which I tended to overuse probably back in my minion days. But you do give up controlled precision in what you do.
2
