Restricted compositions and permutations: From old to new Gray codes
Any Gray code for a set of combinatorial objects defines a total order relation on this set: x is less than y if and only if y occurs after x in the Gray code list. Let < denote the order relation induced by the classical Gray code for the product set (the natural extension of the Binary Reflected Gray Code to k-ary tuples). The restriction of < to the set of compositions and bounded compositions gives known Gray codes for those sets. Here we show that < restricted to the set of bounded compositions of an interval yields still a Gray code. An n-composition of an interval is an n-tuple of integers whose sum lies between two integers: and the set of bounded n-compositions of an interval simultaneously generalizes product set and compositions of an integer, and so < put under a single roof all these Gray codes. As a byproduct we obtain Gray codes for permutations with a number of inversions lying between two integers, and with even/odd number of inversions or cycles. Such particular classes of permutations are used to solve some computational difficult problems. (C) 2011 Elsevier B.V. All rights reserved.
permutations gray codes combinatorial problems (bounded) compositions of an integer inversion table