Download or view 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
}
}
Download or view 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 19967 days, 3 hours, 27 minutes ago.