TAOCPVolume 4A, Section 7.2.1.5 - Generating set partitions. In particular,
the subsection titled Partitions of a multiset and Algorithm M.
This appears to be in the O’Reilly catalog,
which in principle means you should be able to access it through a KCLS or
SPL library account. I haven’t tested this myself since I own the book.
Agenda:
Discuss background motivation: finding “central” conjugate divisors of an
arbitrary integer given its factorization.
This particular case is actually a bit simpler than the general case since
we only need to consider bipartitions.
Building toward a solution:
Warming up with integer partitions.
Next step: set partitions. This can be used to “brute force” the
multipartition problem by building a degenerate map. However, it’s not
efficient. (I’ve been using this for verification.)
First brush at the final goal: multiset partitions. Same as above, but
the original set may contain duplicate elements.
The multipartition generator above works, but it’s not necessarily
efficient. In particular, it uses some exclusion criteria that might entail
a lot of extra work (essentially partially or fully expanding standard set
partitions which are not valid in the case of a particular multiset).
Ultimate goal is to generate multisets in some canonical order. (You further
canonicalize each multipartition by canonicalizing the order of its parts and
and the elements of its parts individually.)
I would like to generate everything in ascending lexicographical order.
However, after working on this on and off for a few weeks, I haven’t yet
found an efficient way to do this. We’ll walk through some of the attempts.
Don Knuth happens to cover this in TAOCP 7.2.1.5. I finally cracked and took
a look at it yesterday. He indeed canonicalizes to make generation efficient,
but does not use lexicographical order in the sense I want to. We’ll try to
unpack this and see if we can adapt it.