paper

Gray-coding through nested sets

arXiv:1502.02625

Abstract

We consider the following combinatorial question. Let be nested sets, where #. A move consists of altering one of the sets , , in a manner so that the nested condition still holds and # is still . Our goal is to find a sequence of moves that exhausts through all subsets of (other than the initial sets ) with no repeats. We call this "Gray-coding through nested sets" because of the analogy with Frank Gray's theory of exhausting through integers while altering only one bit at a time. Our main result is an efficient algorithm that solves this problem. As a byproduct, we produce new families of cyclic Gray codes through binary -bit integers.

arXiv comment16 pages. Feb 11, 2015: some typos corrected