Efficient generation of the binary reflected gray code and its applications

ABSTRACT

Algorithms are presented to generate the n-bit binary reflected Gray code and codewords of fixed weight in that code. Both algorithms are efficient in that the time required to generate the next element from the current one is constant. Applications to the generation of the combinations of n things taken k at a time, the compositions of integers, and the permutations of a multiset are discussed.

REFERENCES

• 1: J. Boothroyd, ACM Algorithm 246: Graycode, Communications of the ACM, v.7 n.12, p.701, Dec. 1964 [doi>10.1145/355588.355589]
• 2: Phillip J. Chase, Algorithm 382: combinations of M out of N objects [G6], Communications of the ACM, v.13 n.6, p.368, June 1970 [doi>10.1145/362384.362502]
• 3: Dershowitz, N. A simplified loop-free algorithm for generating permutations. BIT 15, 2 (1975), 158-164.
• 4: Gideon Ehrlich, Algorithm 466: four combinatorial algorithm [G6], Communications of the ACM, v.16 n.11, p.690-691, Nov. 1973 [doi>10.1145/355611.362541]
• 5: Gideon Ehrlich, Loopless Algorithms for Generating Permutations, Combinations, and Other Combinatorial Configurations, Journal of the ACM (JACM), v.20 n.3, p.500-513, July 1973 [doi>10.1145/321765.321781]
• 6: Flores, I. Reflected number systems. IRE Trans. Electron. Comput. 5, 2 (June 1956), 79-82.
• 7: Gilbert, E.N. Gray codes and paths on the n-cube. Bell Syst. Tech. J. 37, 9 (May 1958), 815-826.
• 8: Gray, F. Pulse code communications. U.S. Patent 2 632 058, March 17, 1953.
• 9: Lenstra, J.W., and Rinnooy Kan, A.H.G. A recursive approach to the generation of combinatorial configurations. Rep. BW 50/75, Mathematisch Centrum, Amsterdam, 1975.
• 10: C. N. Liu , D. T. Tang, Algorithm 452: enumerating combinations of m out of n objects [G6], Communications of the ACM, v.16 n.8, p.485, Aug. 1973 [doi>10.1145/355609.362322]
• 11: Jayadev Misra, Remark on algorithm 246: Graycode [Z], ACM Transactions on Mathematical Software (TOMS), v.1 n.3, p.285, Sept. 1975 [doi>10.1145/355644.356449]
• 12: Tang, D.T., and Liu, C.N. Distance 2-cyclic chaining of constant weight codes. IEEE Trans. Comput. 22, 2 (Feb. 1973), 176-180.

INDEX TERMS

Keywords:
Gray code, combinations, combinatorial computing, compositions, subsets