Gray-coding through nested sets

Original · EN

We consider the following combinatorial question. Let S₀ ⊂ S₁ ⊂ S₂ ⊂...⊂ Sₘ be nested sets, where #(Sᵢ) = i. A move consists of altering one of the sets Sᵢ, 1 ≤ i ≤ m-1, in a manner so that the nested condition still holds and #(Sᵢ) is still i. Our goal is to find a sequence of moves that exhausts through all subsets of Sₘ (other than the initial sets Sᵢ) 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 m-bit integers.