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 20217 days, 23 hours, 31 minutes ago.