Meetup summary

2025-12-05 - Multiset generation - part 1

  • Some example programs for generating all:
  • TAOCP Volume 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.

Notes:

We got through a review of integer partitions and some basics of set partitions. We developed a few different algorithms to generate all integer compositions and partitions. Next time, we’ll give a similar treatment to set partition generation.

tags: