GrayCodes.frink

View or download GrayCodes.frink in plain text format


/** 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
   }
}


View or download GrayCodes.frink in plain text format


This is a program written in the programming language Frink.
For more information, view the Frink Documentation or see More Sample Frink Programs.

Alan Eliasen was born 18659 days, 13 hours, 23 minutes ago.