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.
Abstract
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:
-
Tadao Takaoka,
O(1) Time Algorithms for Combinatorial Generation
by Tree Traversal,
The Computer Journal, 42 (1999) 400-408.
-
Martha Torres, Alfredo Goldman, and Junior Barrera,
A Parallel Algorithm for Enumerating Combinations,
Proceedings of the 2003 International Conference on Parallel
Processing (ICPP '03), IEEE Computer Society, (2003) 581-588.
Back to list of Frank Ruskey's publications.