GrayCode

perman.spad line 1 [edit on github]

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: 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; vv.2.1 is the number of the entry of vv.1 which will be changed next time; 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! 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.