Appendix 1. Lock and key algorithm

The problem of generating all partitions of size p₁,...,p_q from an attribute set, T_m, of melements is equivalent to the problem of selecting q groups of objects, such that there are p_iobjects in group i, from a pool of m objects. The "lock and key algorithm" (reference 9), devised by the author, provides the solution implemented in SPAN.

Suppose the m objects are labelled 1,2,...,m. Let I_i denote the set of objects in group i. If, for the moment, the requirement that all objects in one group are not contained in another is ignored, that is, embedding I_j ⊆ I_i is allowed, there are ^mC_pi possibilities for each I_i. We identify each possibility by a key K_i, where K_i = 1,..., mC_pi and the objects of the q groups are determined by a set keys K₁,...,K_q. By generating a set of keys, the actual objects in each group can be obtained by ünlocking" the combination of each key to obtain I_i.

We discuss generating the keys in a moment. First, consider how to unlock a key K to obtain the combination I = (i₁,...,i_p) of a group of p objects from m. There are ^mC_p combinations and suppose the keys correspond to an ordering in which i_p is incremented the fastest and i1 the slowest. Thus I = (1,2,...,p) corresponds to K = 1, and I = (m-p+1,m-p+2,...,m) corresponds to K = ^mC_p and i₁ < i₂ < ... < i_p. Given i₁ there are L_i1 = ^m-i₁C_p-1 possibilities for the remainingp-1 objects. Thus, if we define

with S₀ = 0 and find an i such that S_i-1 < K ≤ S_i then the first digit is i₁ = i. The remaining combination, i₂,...,i_p is now a permutation of the digits i+1,...,m and K-S_i-1 is the key to unlock the remaining combination. Thus with K , m and p reset to K-S_i-1, m-i, and p-1 respectively we proceed in the same way to find the second digit and so on.

To generate the key combinations K₁,..., K_q consider first the case when p₁ = ,..., = p_q = p. There are c = ^mC_p possible values for each K_i and, to avoid embedding, these have to be distinct. Therefore the problem is that of enumerating the ^cC_q ways to select q objects from c, each enumeration satisfying K₁ < K₂ < ... < K_q. When the p_i's are not all equal, the keys do not necessarily have to satisfy the full inequality K₁ < K₂ < ... < K_q unless p_i-1 = p_i for some iand it is then necessary to ensure that K_i-1 < K_i. Subject to these constraints the sequence of keys can be generated by the simulated nested loop device of Gentleman (reference 3). Except in the special case p₁ = ,..., = p_q = p the algorithm will generate some I_j that are embedded, and in this case it is necessary to check for embedding.

[Back to table of contents]