/** This file contains routines for generating Gray codes with different algorithms. Gray codes are sequences in which at most one element of the sequence changes at a time. See: "Generalized Gray Codes with Applications", Dah-Jyh GUAN https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.119.1344 Savage, Carla Diane (1997). "A Survey of Combinatorial Gray Codes". SIAM Review. Society for Industrial and Applied Mathematics (SIAM). 39 (4): 605–629. CiteSeerX 10.1.1.39.1924. doi:10.1137/S0036144595295272. JSTOR 2132693. http://www4.ncsu.edu/~savage/AVAILABLE_FOR_MAILING/survey.ps */ /** This implements the Guan algorithm (see citation above) for calculating a finite "(n, k)-Gray code" where n is the number of states for each element and k is the number of elements. For example, the binary Gray code with k elements is a "(2,k)-Gray code". This creates a finite-length series with n^k elements. */ grayCode[N, K] := { n = new array[[K+1], N] // The maximum for each digit g = new array[[K+1], 0] // The Gray code; element 0 is LSB u = new array[[K+1], 1] while (g@K == 0) { // Print the current state for j = K-1 to 0 step -1 print[" " + g@j] println[] // enumerate next Gray code i = 0 k = g@0 + u@0 while ((k >= n@i) or (k<0)) { u@i = -u@i i = i+1 k = g@i + u@i } g@i = k } } /** This implements a modification of the Guan algorithm (see citation above) for calculating an infinite "(n, infinity)-Gray code" where n is the number of states for each element and a potentially infinite length. This creates a infinite-length series. */ grayCode[N] := { g = new array[[1], 0] // The Gray code; element 0 is LSB u = new array[[1], 1] while true { // Print the current state for j = length[g]-1 to 0 step -1 print[" " + g@j] println[] // enumerate next Gray code i = 0 k = g@0 + u@0 while ((k >= N) or (k<0)) { u@i = -u@i i = i+1 if i >= length[g] { // Extend arrays g@i = 0 u@i = 1 } k = g@i + u@i } g@i = k } } /** This implements the Guan algorithm (see citation above) for calculating a finite Gray code where each element can have a different number of states. The states are specified in the states array, which contains the possible values that each state can have. Element 0 in the array is the least significant value. Each state can be any Frink expression. For example: args = [array[5 to 7], array[3 to 4]] grayCodeStates[args] */ grayCodeStates[states is array] := { n = deepCopy[states] K = length[states] g = new array[[K+1], 0] // The Gray code; element 0 is LSB u = new array[[K+1], 1] while (g@K == 0) { // Print the current state for j = K-1 to 0 step -1 print[" " + n@j@(g@j)] println[] // enumerate next Gray code i = 0 k = g@0 + u@0 while ((k >= length[n@i]) or (k<0)) { u@i = -u@i i = i+1 if i >= K return k = g@i + u@i } g@i = k } }