Date: 02/16/2001 at 16:51:50 From: Hooman Subject: Gray theory Hi, What is Gray theory? Thanks a lot. Sincerely yours, Hooman
Date: 02/16/2001 at 18:39:30 From: Doctor Anthony Subject: Re: Gray theory Generating n-Tuples of 0's and 1's ----------------------------------- Consider a list of n-tuples of 0's and 1's that has the property that every element differs from its predecessor in only one place. Such a list corresponds to a walk along the edges of an 'n-cube' that visits every CORNER exactly once. Any such walk is called a Gray code of order n. Example: If n = 2, the 'n-cube' will be a square with vertices at (0,0), (0,1), (1,1), and (0,1). (0,1) (1,1) |----------| | | | | | | | | |----------| (0,0) (1,0) A Gray code is (0,0), (1,0), (1,1), (0,1). Note that you could reverse the order of the n-tuples and the list above would still be Gray code. However, you could not swap (0,0) and (1,0), because then successive terms would differ in more than one place and you would not be traversing an edge but jumping across open space. If the terminal corner and initial corner of the walk are separated by one edge (i.e. the last element and the first element in the Gray code differ in only one place), then the Gray code is called 'cyclic'. The Gray code for the 2-cube is cyclic. If n = 3, the 'n-cube' is be an ordinary cube with vertices (0,0,0), (0,0,1), (1,0,1), (1,0,0), (1,1,0), (0,1,0), (0,1,1), and (1,1,1). This list of vertices is also a Gray code for the 3-cube. You should notice that every pair of adjacent terms differs in only 1 place. This means that one of the edges of the cube lies between any two adjacent terms. There are algorithms that allow you to generate the Gray codes (n-tuples of 0's and 1's) for any given n. The topic is related to methods used in generating permutations and combinations - as opposed to just calculating how many there are. - Doctor Anthony, The Math Forum http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.