Loop-Free Sequencing of Bounded Integer Compositions.

We modify the Knuth-Klingsberg Gray code for unrestricted integer compositions to obtain a Gray code for integer compositions each of whose parts is bounded between zero and some positive integer. We also generalize Ehrlich’s method for loop-free sequencing to implement this Gray code in \(O(1)\) worst-case time per composition. The \((n-1)\)-part compositions of \(r\) whose \(i\)th part is bounded by \(n-i\) are the inversion vectors of the permutations of \(\{1,\ldots,n\}\) with \(r\) inversions; we thus obtain a Gray code and a loop-free sequencing algorithm for this set of permutations.