Efficient generation of the binary reflected gray code and its applications
James R. Bitner, Gideon Ehrlich, Edward M. Reingold · Communications of the ACM · 1976
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.
Cited by 240 works. doi:10.1145/360336.360343 Open-access PDF
Authors
References
- Gray Codes and Paths on the n-Cube
- Loopless Algorithms for Generating Permutations, Combinations, and Other Combinatorial Configurations
- On the Parallel Evaluation of Polynomials
- Algorithm 382: combinations of M out of N objects [G6]
- Reflected Number Systems
- Algorithm 466: four combinatorial algorithm [G6]
- Distance-2 Cyclic Chaining of Constant-Weight Codes
- Algorithm 452: enumerating combinations of m out of n objects [G6]
- A recursive approach to the generation of combinatorial configurations
- Remark on algorithm 246