# GrayCodes.frink

``` /** 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[, 0]  // The Gray code; element 0 is LSB    u = new array[, 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    } } ```