/usr/share/axiom-20170501/src/algebra/GRAY.spad is in axiom-source 20170501-3.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 | )abbrev package GRAY GrayCode
++ Authors: Johannes Grabmeier, Oswald Gschnitzer
++ Date Created: 7 August 1989
++ Date Last Updated: 23 August 1990
++ References:
++ Henryk Minc: Evaluation of Permanents,
++ Proc. of the Edinburgh Math. Soc.(1979), 22/1 pp 27-32.
++ Nijenhuis and Wilf : Combinatorical Algorithms, Academic
++ Press, New York 1978.
++ S.G.Williamson, Combinatorics for Computer Science,
++ Computer Science Press, 1985.
++ Description:
++ GrayCode provides a function for efficiently running
++ through all subsets of a finite set, only changing one element
++ by another one.
GrayCode() : SIG == CODE where
PI ==> PositiveInteger
I ==> Integer
V ==> Vector
SIG ==> with
nextSubsetGray : (V V I,PI) -> V V I
++ nextSubsetGray(ww,n) returns a vector vv whose components
++ have the following meanings:\br
++ 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;\br
++ vv.2.1 is the number of the entry of vv.1 which
++ will be changed next time;\br
++ 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!\br
++
++ The other components of vv.2 are needed to compute
++ nextSubsetGray efficiently.
++ Note that this is an implementation of [Williamson, Topic II, 3.54,
++ p. 112] for the special case r1 = r2 = ... = rn = 2;
++ Note that nextSubsetGray produces a side-effect,
++ nextSubsetGray(vv) and vv := nextSubsetGray(vv)
++ will have the same effect.
firstSubsetGray : PI -> V V I
++ firstSubsetGray(n) creates the first vector ww to start a
++ loop using nextSubsetGray(ww,n)
CODE ==> add
firstSubsetGray(n : PI) ==
vv : V V I := new(2,[])
vv.1 := new(n,0) @ V I
vv.2 := new(n+1,1) @ V I
for i in 1..(n+1) repeat
vv.2.i := i
vv
nextSubsetGray(vv : V V I,n : PI) ==
subs : V I := vv.1 -- subset
lab : V I := vv.2 -- labels
c : I := lab(1) -- element which is to be changed next
lab(1):= 1
if subs.c = 0 then subs.c := 1
else subs.c := 0
lab.c := lab(c+1)
lab(c+1) := c+1
vv
|