# In what order does Combinatorica's SetPartitions function list the partitions of a set?

For example,

Needs["Combinatorica"]
n = 4;
partitions = SetPartitions[Range[n]];
Table[Print[partitions[[i]]], {i, 1, BellB[n]}]


generates

{{1,2,3,4}}
{{1},{2,3,4}}
{{1,2},{3,4}}
{{1,3,4},{2}}
{{1,2,3},{4}}
{{1,4},{2,3}}
{{1,2,4},{3}}
{{1,3},{2,4}}
{{1},{2},{3,4}}
{{1},{2,3},{4}}
{{1},{2,4},{3}}
{{1,2},{3},{4}}
{{1,3},{2},{4}}
{{1,4},{2},{3}}
{{1},{2},{3},{4}}


(and a bunch of Nulls !)

I notice that the coarsest ordering of these partitions is in increasing order of the number of parts, $$k$$. Also the partitions are written such that the elements of each part are in increasing order, and the parts are in increasing order of their least (hence also first appearing) element. I notice that for each $$k$$ (the number of parts), the partitions having $$\{1\}$$ as a singleton set are listed first, and that this rule seems to be applied recursively to the partition of the remaining set.

@Mr.Wizard gives some nice code here, for generating the same partitions, that happens to order the partitions differently.

• "bunch of Nulls" - because the result of Print[] is Null, which gets passed to Table[]. Try Scan[Print, partitions]` if you wish for a one-by-one printout. As for the ordering, IIRC this is in lexicographic order. – J. M. will be back soon Sep 25 '18 at 20:30
• Unlike almost everything else in Mathematica, all the source code for all the Combinatorica functions is in the Combinatorica.m file down inside the Mathematica folder tree. You can open and read that file with Mathematica, just be careful you don't damage the file. If the definition of SetPartitions was huge and incomprehensible it would be one thing, but the definition is only a few lines and most of the work is passed off to another function in the file, which is also only a few lines. Perhaps this can help you understand how it works. – Bill Sep 26 '18 at 4:29
• Thank you so much, Bill ! That is brilliant ! I have copied and renamed from that file about 11 commands that I directly or indirectly use, and having looked at them and understood them, maybe I'll post an answer to my own question here. – Simon Sep 26 '18 at 21:00
• J. M., I failed to notice your comment about the ordering until now - thank you for that. I believe I've read that Mathematica orders partitions of integers reverse lexicographically. However, the example above refutes the conjecture that it orders set partitions by a refinement of any partial order according to their integer partition type. For example, the 2nd and 4th items have a common integer partition type (3, 1), yet they are separated by the 3rd, whose type is (2, 2). – Simon Sep 27 '18 at 12:05