Ranking Algorithms for Lists of Partitions
S. Gill Williamson · SIAM Journal on Computing · 1976
Given an algorithm for producing a list of objects, a “ranking” algorithm or “sequential numbering scheme“ is a rule $\rho $ which, given an object x, computes its position $m = \rho (x)$ in the list. The associated algorithm for computing $\rho ^{ - 1} $, produces the object x given its position m. In this paper, we consider the objects to be various classes of partitions of a set S. We consider ranking algorithms for lists of all ordered partitions, ordered partitions corresponding to a given multinomial index, all unordered partitions, unordered partitions with a bounded number of blocks, unordered partitions with a fixed number of blocks, unordered partitions with blocks of equal size, unordered partitions corresponding to a fixed ordered partition, and unordered partitions of specified block type. These ranking algorithms are frequently useful for organizing computations associated with the above lists. The computation of $\rho ^{ - 1} $ at a randomly selected m provides a method for the random selection of elements from any of these lists.