Abstract: A Gray Code for Combinations of a Multiset

Frank Ruskey, Department of Computer Science, University of Victoria, Canada.
Carla Savage, Department of Computer Science, North Carolina State University.


Let C(k;n0,n1,...,nt) denote the set of all k-element combinations of the multiset consisting of ni 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. Selected Citations:
Back to list of Frank Ruskey's publications.