GrayCode¶

GrayCode provides a function for efficiently running through all subsets of a finite set, only changing one element by another one.

firstSubsetGray: PositiveInteger -> Vector Vector Integer: firstSubsetGray(n) creates the first vector ww to start a loop using nextSubsetGray(ww, n)

nextSubsetGray: (Vector Vector Integer, PositiveInteger) -> Vector Vector Integer: nextSubsetGray(ww, n) returns a vector vv whose components have the following meanings: begin{items} item vv.1: a vector of length n whose entries are 0 or 1. This can be interpreted as a code for a subset of the set 1, …, n; vv.1 differs from ww.1 by exactly one entry; item vv.2.1 is the number of the entry of vv.1 which will be changed next time; item vv.2.1 = n+1 means that vv.1 is the last subset; trying to compute nextSubsetGray(vv) if vv.2.1 = n+1 will produce an error! end{items} The other components of vv.2 are needed to compute nextSubsetGray efficiently. Note: this is an implementation of [Williamson, Topic II, 3.54, p. 112] for the special case r1 = r2 = … = rn = 2; Note: nextSubsetGray produces a side-effect, i.e. nextSubsetGray(vv) and vv := nextSubsetGray(vv) will have the same effect.