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.
1
1
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)
Replying to
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
Replying to
Looks a bit like a Galois group decomposition diagram (forgot what they're meant to be called)

