Fast algorithms to generate Beckett-Gray codes and coil-in-the-box codes
Dennis Wong · The Atrium (University of Guelph) · 2007
A Gray code is an ordering of combinatorial objects such that any two successive objects differ by some pre-specified constant amount. Gray codes and their related data structures are integral in solving a diverse set of problems. Fast algorithms to generate all possible ordering of combinatorial objects are sought. The number of Gray codes on binary strings of length one to five are 1, 2, 18, 5712 and 5859364320 respectively. Since the computation tree for ' n' >= 6 is so large that an exhaustive generation remains impractical, much of the focus is on generating restricted class or variant of Gray codes on binary strings. In this thesis, we study algorithms for generating Beckett-Gray codes and coil-in-the-box codes, which are a restricted class and a variant of Gray codes on binary strings respectively. We provide several heuristics to improve the efficiency of generating Beckett-Gray codes and coil-in-the-box codes. There is an improvement by a factor of approximately 60 and 17 on the runtime for generating all 6-bit Beckett-Gray codes and 7-bit coil-in-the-box codes when compared to the fastest previously known algorithms respectively.