Loop-free Gray code algorithms for the set of compositions (Q655198)

The topic of Gray codes for the set of compositions with non-negative integer parts has been studied by several authors. Klingsberg gave a non-recursive description of a Gray code for this set after the recursive version of Knuth. Recently, Walsh modified Klingsberg's algorithm to find a Gray code which generates the set of all bounded compositions with non-negative integer parts. In this paper, the authors present two loopless Gray code algorithms for the set of compositions with positive integer parts. Each composition is obtained from its predecessor by either incrementing one part by 1 and decrementing another part by 1, or substracting \(i\) from a part and inserting \(i\) to the right of the composition. In an appendix the authors present their algorithms in C++.