A Gray Code for Combinations of a Multiset

Frank Ruskey ^{∗}

Department of Computer Science

University of Victoria Victoria, B.C., V8W 3P6, Canada

Carla Savage ^{†}

Department of Computer Science North Carolina State University Raleigh, North Carolina, 27612-8206

∗Research supported by NSERC grant A3379.

†Research supported by National Science Foundation Grant No. CCR8906500 and National Security Agency Grant No. MDA904-H-4001.

Proposed Running Head:

Multiset Combinations

Direct correspondence, proofs, etc. to:

Carla D. Savage Department of Computer Science

Box 8206

North Carolina State University

Raleigh, NC 27695-8206 USA

Abstract

Let C(k; n_{0}, n_{1}, …, n_{t}) denote the set of all k-element combinations of the multiset consisting of n_{i} occurrences of i for i = 0, 1, …, t. Each combination is itself a multiset. For example, C(2; 2, 1, 1) = {{0, 0}, {0, 1}, {0, 2}, {1, 2}}. We show that multiset combinations can be listed so that successive combinations differ by one element. Multiset combinations simultaneously generalize compositions and combinations, for which minimal change listings, called Gray codes, are known.

1 Introduction

By C(k; n_{0}, n_{1}, …, n_{t}) we denote the set of all ordered (t + 1)-tuples (x_{0}, x_{1}, …, x_{t}) satisfying

x_{0} + x_{1} + ⋯ + x_{t} = k where 0 ≤ x_{i} ≤ n_{i} for i = 0, 1, …, t.  (1)

We assume throughout the paper that n_{i} is a positive integer for i = 0, 1, …, t. Solutions to (1) are referred to as combinations of a multiset because they can be regarded as k-subsets of the multiset consisting of n_{i} copies of i for 0 ≤ i ≤ t. Solution (x_{0}, x_{1}, …, x_{t}) corresponds to the k-subset consisting of x_{i} copies of i for 0 ≤ i ≤ t. For example, C(2; 2, 1, 1) corresponds to {{0, 0}, {0, 1}, {0, 2}, {1, 2}}. When each n_{i} is 1, the set C(k; n_{0}, n_{1}, …, n_{t}) is simply the set of all combinations of t + 1 elements chosen k at a time.

Alternatively, the elements of C(k; n_{0}, n_{1}, …, n_{t}) can be regarded as placements of k identical balls into t + 1 labeled boxes where the ith box can hold at most n_{i} balls, i.e., compositions of k into t+1 parts in which the ith part is at most n_{i}. Under this interpretation, C(2; 2, 1, 1) = {(0, 1, 1), (1, 0, 1), (1, 1, 0), (2, 0, 0)}. When each n_{i} is at least k, C(k; n_{0}, n_{1}, …, n_{t}) is the set of all compositions of k into t + 1 parts.

These are frequently occurring combinatorial objects, and it is natural to consider efficient algorithms for generating them. In particular, we will focus on listing multiset combinations in a minimal change order. Minimal change listings of combinatorial objects are called Gray codes, after Frank Gray, who patented a scheme for listing n-bit strings so that successive strings differ in just one bit [9].

We adopt the convention that lower case bold letters represent (t + 1)-tuples; e.g., a = (a_{0}, a_{1}, …, a_{t}). Two elements x, y of C(k; n) are adjacent if there are indices p and q such that x_{i} = y_{i} for i ≠ p, q, where in addition x_{p} = y_{p} + 1 and x_{q} = y_{p} − 1. This concept of adjacency seems to be the most natural one for solutions in integers to an equation of the form x_{0} + x_{1} + ⋯ + x_{t} = k, possibly subject to some other side constraints. It has been applied to combinations (e.g., Bitner, Ehrlich and Reingold [1] or Eades and McKay [4]), compositions (e.g., as attributed to Knuth in Wilf [14]), and to integer partitions (e.g., Savage [13], Rasmussen, Savage and West [11]). For each of these classes, it was shown that there is an exhaustive listing of the elements in which successive elements on the list are adjacent under this criterion.

In this paper, we seek a listing of the elements of C(k; n) in which successive elements are adjacent. Such a listing will be referred to as a Gray code for combinations of a multiset.

The problem of efficiently generating the combinations of a multiset (in any order) was also given in Reingold, Nievergelt, and Deo [12] (pg. 201, exercise 23), but the associated solutions manual by Fill and Reingold [8] contains no solution. A loopfree algorithm, called COMPOMAX, was developed by Ehrlich [5], [6]. In Ehrlich’s algorithm successive solutions differ in two adjacent positions, but in those positions the elements may differ by more than one from their previous values. Roelants van Baronaigien, Ruskey, and Engels [7] provide a simpler constant amortized time generation algorithm which, however, is not a Gray code; it generates the combinations in lexicographic order.

2 The Construction

Define a multiset combination x to be left extreme if x_{i} > 0 implies either i = 0 or x_{i−1} = n_{i−1} and right extreme if x_{i} > 0 implies i = n or x_{i+1} = n_{i+1}. Equivalently, x is left (right) extreme if it is maximum (minimum) in C(k; n) in the lexicographic ordering of (t + 1)-tuples. For example, in C(2; 2, 1, 1), (2, 0, 0) is left extreme and (0, 1, 1) is right extreme. Let n = n_{0} + n_{1} + ⋯ + n_{t}. Left and right extreme multiset combinations are unique, although a multiset combination is both left and right extreme if k = 0 or k = n, since in these cases C(k; n) has only one element. We call a Gray code for combinations of a multiset extreme if it starts with the right extreme combination and ends with the left extreme combination.

Lemma 1 If both C(k; n) and C(k+1; n) are nonempty then their right (left) extreme elements differ in only one position, and in that position by one.

Proof. If (x_{0}, x_{1} …, x_{t}) is right extreme for C(k; n), there is an index j, 0 ≤ j ≤ t such that x_{i} = 0 for 0 ≤ i < j and x_{i} = n_{i} for t ≥ i > j. Then the right extreme element of C(k + 1; n) is obtained by adding 1 to x_{j} if x_{j} < n_{j} and otherwise by adding 1 to x_{j−1}. The left extreme case is similar. □

Our Gray code construction is recursive, with the basis cases covered in Lemmas 2 and 3 and the general case in Theorem 1. If x ∈ C(k; n), then x_{t} must satisfy

max(0, k − n + n_{t}) ≤ x_{t} ≤ min(n_{t}, k).

Thus, when t ≥ 1, C(k; n) can be partitioned as the disjoint union

C(k; n) = ⨄_{x_{t}=max(0,k−n+n_{t})}^{min(n_{t},k)} C(k − x_{t}; n_{0}, …, n_{t−1}).

Let G(k; n) be the graph whose vertex set is C(k; n), and where edges exist between vertices that are adjacent. A Gray code for C(k; n) is a Hamilton path in G(k; n).

Lemma 2 There is an extreme Gray code listing of C(k; n) when t = 1 and 0 ≤ k ≤ n.

Proof: Let p = max(0, k − n_{1}) and q = max(0, k − n_{0}). In this case G(k; n_{0}, n_{1}) is a path and there is only one possible list as shown below.

(p, k − p), (p + 1, k − p − 1), …, (k − q, q).
□

Lemma 3 There is a Gray code listing of C(k; n) when t = 2, which is extreme unless n_{0} = n_{2} = 1 and 2 ≤ k ≤ n_{1}.

Proof: Here it is helpful to consider the graph G(k; n_{0}, n_{1}, n_{2}), one instance of which is shown in Figure 2. The solid squares represent the extreme vertices. Some variation of this figure can occur, depending upon the location of the lines x_{0} + x_{1} = k and x_{0} + x_{1} = k − n_{2}.

Figure 2 shows a construction that yields a Hamilton path between the two extreme vertices. The path is constructed a column at a time, from left-to-right, with the possible exception of the rightmost two columns, where a zig-zag path from bottomto-top may be necessary. This construction works so long as n_{0} > 1. If n_{0} = 1, then it is possible to zig-zag from one extreme to the next, unless n_{2} = 1 and n_{1} ≥ k ≥ 2. In this case, C(k; 1, n_{1}, 1) has four elements which can be listed in Gray code order as (0, k − 1, 1), (0, k, 0), (1, k − 1, 0), (1, k − 2, 1). □

Lemma 4 If there is an extreme Gray code for C(k; n), then there is an extreme Gray code for C(n − k; n).

[figure: 0; 1; 2; ⋯; n_{0}; 0; 1; 2; ⋮; n_{1}; x_{0} + x_{1} = k − n_{2}; x_{0} + x_{1} = k; decreasing x_{2}]

Figure 1: The graph G(k; n_{0}, n_{1}, n_{2}).

[figure]

Figure 2: Extreme Gray codes (a) n_{0} even, (b) n_{0} odd.

A = ( \begin{matrix}0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 \end{matrix} ) B = ( \begin{matrix}0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 \end{matrix} )

C = ( \begin{matrix}0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 \end{matrix} ) D = ( \begin{matrix}0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \end{matrix} )

Figure 3: Path matices arising in the proof of Theorem 1.

Proof: Given x = (x_{0}, x_{1}, …, x_{t}) in C(k; n), define ϕ(x) = y, where y_{i} = n_{i} − x_{i} for i = 0, 1, …, t. Now observe that ϕ is a graph isomorphism between G(k; n) and G(n − k; n). It is also clear that a left extreme vertex in G(k; n) is right extreme in G(k; n), and vice-versa. □

The following technical lemma will be used in Theorem 1 below to show the existence of a Gray code in C(k; n). Let [1] denote the 4 by 4 Boolean matrix with all entries 1.

Lemma 5 Let A, B, C, and D be the four Boolean matrices in Figure 3. Let M be the Boolean product, M = M_{1}M_{2} ⋯ M_{k}, where k ≥ 2 and M_{i} ∈ {A, B, C, D, [1]} for 1 ≤ i ≤ k. Then M = [1] unless M_{1} = M_{2} = ⋯ = M_{k}.

Proof. It can be checked that the product of any two distict matrices from {A, B, C, D, [1]} is [1]. Thus, M = [1] if at least two different matrices are factors in the product M_{1} = M_{2} = ⋯ = M_{k}. □

Note that in constructing a Gray code for C(k; n), it suffices to consider the cases where n is nondecreasing : n_{0} ≤ n_{1} ≤ … ≤ n_{t}. For, if π is a permutation of {0, …, t} and n_{π} = (n_{π(0)}, n_{π(1)}, …, n_{π(t)}), a Gray code for C(k; n_{π}) can be obtained from a Gray code for C(k; n) by permuting the coordinates by π. However, this permutation does not preserve extreme elements. Theorem 1 below guarantees an extreme Gray code for all C(k; n) with nondecreasing n, and therefore a Gray code (not necessarily extreme) for all multiset combinations.

Theorem 1 For all k ≥ 0 and non-decreasing n, there is an extreme Gray code for C(k; n).

L:

(Extreme Gray

code for C(5; 2 + 2, 2 + 4)

= C(5; 4, 6))

i  (w_{i}, z_{i})  C_{i} =  M_{z}^{(i)}  M_{w}^{(i)}
C(z_{i}; 2, 2)  Extreme Gray Extreme Gray
×C(w_{i}; 2, 4) code for code for
C(z_{i}; 2, 2)  C(w_{i}; 2, 4)

1  (0,5)  C(0; 2, 2) × C(5; 2, 4)  (0,0)  (1,4)

(2,3)

2  (1,4)  C(1; 2, 2) × C(4; 2, 4)  (0,1)  (0,4)
(1,0)  (1,3)

(2,2)

3  (2,3)  C(2; 2, 2) × C(3; 2, 4)  (0,2)  (0,3)
(1,1)  (1,2)
(2,0)  (2,1)
4  (3,2)  C(3; 2, 2) × C(2; 2, 4)  (1,2)  (0,2)
(2,1)  (1,1)

(2,0)

5  (4,1)  C(4; 2, 2) × C(1; 2, 4)  (2,2)  (0,1)

(1,0)

Figure 4: Example: Gray code construction in Theorem 1 for C(5; 2, 2, 2, 4).

Proof: The case t = 0 is trivial or empty, and the cases t = 1 and t = 2 are covered by Lemmas 2 and 3. So we assume that t ≥ 3 and proceed by induction on t. By Lemma 4 we may assume also that k ≤ n/2. Let x be right extreme. Since x has at least four coordinates, arranged in nondecreasing order, x_{0} = x_{1} = 0. Now consider the problem of listing the solutions to z +w = k, where 0 ≤ z ≤ n_{0} +n_{1} and 0 ≤ w ≤ n_{2} +⋯+n_{t}. By Lemma 2, there is an extreme Gray code for this set, namely

L = (z_{1}, w_{1}), (z_{2}, w_{2}), …, (z_{m}, w_{m}),

where (z_{i}, w_{i}) = (i − 1, k − i + 1) and w_{m} = max(0, k − (n_{0} + n_{1})). For 1 ≤ i ≤ m, let C_{i} be the subset of C(k; n) defined by

C_{i} = C(z_{i}; n_{0}, n_{1}) × C(w_{i}; n_{2}, n_{3}, … n_{t}),

and let G_{i} be the subgraph of G(k; n) induced by C_{i}. Then

C(k; n) = ⋃_{i=1}^{m} C_{i}.

(See Figure 4 for an example.)

To prove the existence of a Gray code for C(k; n), we show that each C_{i} has a Gray code, L_{i}, satisfying:

(i) For 1 ≤ i < m, the last element of L_{i} is adjacent to the first element of L_{i+1}, (ii) the first element of L_{1} is right extreme, and (iii) the last element of L_{m} is left extreme.

Then L_{1}, L_{2}, …, L_{m} is an extreme Gray code for C(k; n).

By induction, there exist extreme Gray codes

M_{z}^{(i)} for C(z_{i}; n_{0}, n_{1}) from r_{z}^{(i)} to l_{z}^{(i)} and  (2)
M_{w}^{(i)} for C(w_{i}; n_{2}, …, n_{t}) from r_{w}^{(i)} to l_{w}^{(i)}.  (3)

(See example in Figure 4.) Thus, G_{i} has as a spanning subgraph a grid graph, denoted H_{i}, in which (x_{0}, … x_{t}) is adjacent to (y_{0}, … y_{t}) if either

(x_{0}, x_{1}) is the successor of (y_{0}, y_{1}) on M_{z}^{(i)} and x_{j} = y_{j} for i > 1, or
(x_{2}, … x_{t}) is the successor of (y_{2}, … y_{t}) on M_{w}^{(i)} and x_{i} = y_{i} for i = 0, 1.

(See Figure 5 for the grids in the example of Figure 4). The four corners of H_{i} correspond to the four different pairs of extreme elements: (r_{z}^{(i)}, r_{w}^{(i)}), (r_{z}^{(i)}, l_{w}^{(i)}), (l_{z}^{(i)}, l_{w}^{(i)}), and (l_{z}^{(i)}, r_{w}^{(i)}); we refer to those corners as rr, rl, ll, lr, respectively. (If (2) has only one element, then rr = lr and rl = ll; if (3) has only one element, then rr = rl and lr = ll.) Note that by Lemma 1, for 1 ≤ i < m, corresponding corners of H_{i} and H_{i+1} are adjacent.

Our strategy is to connect hamilton paths through successive grid graphs at their corners in such a way that we end and start at the extreme elements of C(k; n).

Depending upon the dimensions of a grid graph, H_{i}, only certain corners of H_{i} may be connected by Hamilton paths in H_{i}. The four possibilities are summarized by the path matrices shown in Figure 3. below. Both the rows and columns of these matrices are indexed rr, rl, ll, lr. A ‘1’ entry indicates that there is a Hamilton path between the corners, and a 0 indicates that there is no such Hamilton path. Matrix A corresponds to an r by c grid graph with r and c both odd; matrix B to r odd, c even; matrix C to r even, c odd; matrix D to r even, c even. If r = c = 1, matrix 1 represents the possible hamilton paths. Otherwise, if r = 1, use matrix B or if c = 1, use matrix C.

Let P_{i} be the path matrix for H_{i}. For 1 ≤ i ≤ m, we want a hamilton path q_{i} in H_{i} which starts and ends at a corner of H_{i} such that q_{1} starts in corner rr (right extreme,) q_{m} ends in corner ll (left extreme,) and for 1 ≤ i < m, q_{i} ends in the corner of H_{i} corresponding to the corner of H_{i+1} in which q_{i+1} begins. This is possible if and only if the product P = P_{1}P_{2} ⋯ P_{m} has entry P [rr, ll] equal to 1. By Lemma 5, it suffices to show that either m = 1 and P_{1}[rr, ll] = 1 or that the sequence P_{1}, P_{2}, … P_{m} contains at least two distinct elements.

The first entry of L is always (z_{1}, w_{1}) = (0, k). Thus, C_{1} = C(0; n_{0}, n_{1}) × C(k; n_{2}, …, n_{t}). The first factor contains only the element (0, 0), so H_{1} has only one row and therefore P_{1} ∈ {[1], B}. If m = 1, the result follows. Otherwise, m ≥ 2, (z_{2}, w_{2}) = (1, k − 1) and C_{2} = C(1; n_{0}, n_{1}) × C(k − 1; n_{2}, …, n_{t}). The first factor of C_{2} contains exactly two elements (0, 1) and (1, 0), so that H_{2} has two rows and therefore P_{2} ∉ { 1,B}. Then by Lemma 5 the product P_{1}P_{2} ⋯ P_{m} = [1] since P_{1} and P_{2} are distinct. □

3 Final Remarks

An open problem is to find Gray codes where the x_{i} that change are adjacent. In that case the underlying graph is bipartite and we may compute the difference in the sizes

[figure: (1,0,0,4); (1,0,1,3); (1,0,2,2); (1,1,0,3); (1,1,1,2); (1,1,2,1); (2,0,0,3); (2,0,1,2); (2,0,2,1); (0,1,0,4); (0,0,2,3); (0,1,0,4); (0,1,1,3); (0,1,2,2); (0,2,0,3); (0,2,1,2); (0,2,2,1); (1,2,0,2); (1,2,1,1); (1,2,2,0); (2,1,0,2); (2,1,1,0); (2,1,2,0); (2,2,0,1); (2,2,1,0); H_{1}; (type B); H_{2}; (type C); H_{3}; (type A); H_{4}; (type C); H_{5}; (type B)]

Figure 5: The grid graphs for the example in Figure 4. Gray code in C(5; 2, 2, 2, 4) can be obtained by using indicated adjacency links between grids. of the partite sets. If the difference is greater than one, then there is no Gray code.

Given a solution x to (1), define the weight, w(x), of x as

w(x_{0}, …, x_{t}) = x_{0} + x_{2} + ⋯ = ∑_{i even} x_{i}.

Observe that moving a ball from one box to an adjacent box changes the parity of the weight. Define the parity difference d(k; n) to be

d(k; n) = ∑_{x∈C(k;n)}(−1)^{w(x)}

The parity difference satisfies the following recurrence relation.

d(k; n) = \{ \begin{matrix}+1 & if t = 0 and k even \\ −1 & if t = 0 and k odd \\ ∑_{i=max(0,k−n+n_{t})}^{min(n_{t},k)} d(k − i; n_{0}, …, n_{t−1}) & if t > 0 odd \\ ∑_{i=max(0,k−n+n_{t})}^{min(n_{t},k)}(−1)^{i}d(k − i; n_{0}, …, n_{t−1}) & if t > 0 even \end{matrix}

This recurrence can be solved if all n_{i} = 1. See, for example, Buck and Wiedemann [2], Eades, Hickey and Read [3], Ko and Ruskey [10]. Then

d(k; 1) = \{ \begin{matrix}0 & if t and k are odd \\ \binom{⌊(t+1)/2⌋}{⌊k/2⌋} & otherwise. \end{matrix}

By similar reasoning, it can also be solved when all n_{i} = ∞.

d(k; ∞) = \{ \begin{matrix}0 & if t and k are odd \\ \binom{⌊(t+k)/2⌋}{⌊k/2⌋} & otherwise \end{matrix}

We close by mentioning three open problems:

• Determine exact conditions under which the parity difference is zero.

• Develop an algorithm for generating the Hamilton path in G(k; n) that runs in time proportional to |C(k; n)|.

• This paper shows the existence of a Hamilton path in G(k; n). We believe that there is a Hamilton cycle in G(k; n) whenever t > 1.

References

[1] J. Bitner, G. Ehrlich, and E. Reingold, Efficient Generation of the Binary Reflected Gray Code and its Applications, Communications of the ACM, 19 (1976) 517-521.

[2] M. Buck and D. Wiedemann, Gray Codes with Restricted Density, Discrete Mathematics, 48 (1984) 163-171.

[3] P. Eades, M. Hickey and R. Read, Some Hamilton Paths and a Minimal Change Algorithm, Journal of the ACM, 31 (1984) 19-29.

[4] P. Eades and B. McKay, An Algorithm for Generating Subsets of Fixed Size with a Strong Minimal Change Property, Information Processing Letters, 19 (1984) 131-133.

[5] G. Ehrlich, Algorithm 466: Four combinatorial algorithms, Communications of the ACM, 16 (1973) 690-691.

[6] G. Ehrlich, Loopless Algorithms for Generating Permutations, Combinations and Other Combinatorial Configurations, Journal of the ACM, 20 (1973) 500-513.

[7] W. Engels, D. Roelants van Baronaigien, and F. Ruskey Generating Combinations of a Multiset, manuscript, 1993.

[8] J.A. Fill and E.M. Reingold, Solutions Manual for Combinatorial Algorithms: Theory and Practice, Prentice-Hall, 1977.

[9] F. Gray, Pulse code communication, U. S. Patent 2632058 (1953).

[10] C.W. Ko and F. Ruskey, Solution of Some Multi-dimensional Lattice Path Parity Difference Recurrence Relations, Discrete Mathematics, 71 (1988) 47-56.

[11] D. J. Rasmussen, C.D. Savage and D.B. West, Gray Code Enumeration of Families of Integer Partitions , Journal of Combinatorial Theory, Series A, to appear.

[12] E.M. Reingold, J. Nievergelt, and N. Deo, Combinatorial Algorithms: Theory and Practice, Prentice-Hall, 1977.

[13] C.D. Savage, Gray Codes Sequences of Partitions, J. Algorithms, 10 (1989) 577-595.

[14] H.S. Wilf, Combinatorial Algorithms: An Update, SIAM, CBMS 55, 1989.