Gray Codes, Loopless Algorithms and Set Partitions
Toufik Mansour · 2012
Algorithms and their analysis play an important role in both mathematics and computer science. In particular, many algorithms make a list of all or some of the objects of a combinatorial class (see Definition 1.31). In this chapter; we are interested in efficient object listing algorithms for such combinatorial classes. Researchers in computer science are interested in finding generating algorithms for combinatorial classes. More precisely, they seek efficient generating members in a particular combinatorial class in such a way that each member is generated exactly once. Many generating problems require sampling the members of the class. Whereas early work on combinatorics focused on counting, as we saw in the previous chapters, the computer used to list the members of the combinatorial class. However, in order to present such a listing, our generating method needs to be extremely efficient. In 1973, Ehrlich [102] suggested a new approach for generating the members of a combinatorial class in which successive elements differ in a “small change”. The classic example is the binary reflected Gray code [114, 124], which gives a listing of binary words of size n so that successive members differ in exactly one letter, as described in Example 9.5. Such a listing has two advantages: generation of the list of members of the combinatorial class might be faster and the consecutive members which by differ in “small changes” could differ by only small computations. Finally, Gray codes typically involve elegant recursive structures, which throw new light on the combinatorial class structure.