3
$\begingroup$

A (binary) Gray code is a sequence of bit strings that run through all $2^n$ strings in $\{0,1\}^n$, and where successive strings differ by only one bit. Here's a $3$-bit Gray code, where the strings are written as columns:

$00001111$
$00111100$
$01100110$

A single-track Gray code has the property that each row is identical up to offsets (i.e., cyclical shifts). It is impossible for such a code to run through all $2^n$ strings, so this condition is relaxed. Here's a $5$-bit single-track Gray code, with red zeroes showing the offsets:

$\color{red}00000001110001111111$
$1111\color{red}0000000111000111$
$01111111\color{red}000000011100$
$110001111111\color{red}00000001$
$0001110001111111\color{red}0000$

Note that the above code is not maximal in the sense that it only runs through $20$ words, while it is possible for a $5$-bit single-track Gray code to run through up to $30$ words. But that's fine. Also note that the offsets are evenly spaced. That's not strictly necessary.

Question: I am looking for ternary (or higher $k$-ary) single-track Gray codes for small values of $n$ (say $3 \leq n \leq 6$). In other words, the codes would run through (some of) the strings in $\{0,1,2\}^n$ without repeats, where successive strings differ in one place. The codes don't need to be maximal, and the offsets don't need to be evenly spaced. Any ideas?


Joriki's code, for posterity:

import java.util.Random;
import java.util.Stack;

public class Question1676642 {
    final static int k = 3;
    final static int n = 6;

    public static void main (String [] args) {
        int record = 0;
        Random random = new Random ();
        Stack<int []> words = new Stack<int[]> ();

        outer:
        for (;;) {
            words.clear ();
            int [] first = null;
            int [] next = null;
            int failCount = 0;

            for (;;) {
                if (words.isEmpty ()) {
                    first = next = new int [n];
                    for (int i = 0;i < n;i++)
                        next [i] = random.nextInt (k);
                }
                else {
                    next = words.get (words.size () - 1).clone ();
                    int index = random.nextInt (n);
                    int value = random.nextInt (k - 1) + 1;
                    next [index] += value;
                    next [index] %= k;
                }

                words.push (next);

                boolean valid = true;
                for (int [] word : words)
                    for (int i = 0;i < n;i++)
                        if (word != next || i != 0) {
                            boolean same = true;
                            for (int j = 0;j < n;j++)
                                same &= next [j] == word [(j + i) % n];
                            valid &= !same;
                        }

                if (valid) {
                    failCount = 0;
                    if (words.size () > record)
                        for (int d = -1;d <= 1;d += 2) {
                            int diffs = 0;
                            for (int i = 0;i < n;i++)
                                if (first [i] != next [(i + d + n) % n])
                                    diffs++;
                            if (diffs == 1) {
                                System.out.println ("words: " + words.size ());
                                for (int i = 0;i < n;i++) {
                                    System.out.print ("    ");
                                    for (int j = 0;j < words.size ();j++)
                                        System.out.print (words.get (j) [i]);
                                    System.out.println ();
                                }
                                System.out.println ();
                                record = words.size ();
                            }
                        }
                }
                else {
                    words.pop ();
                    if (++failCount == 100)
                        continue outer;
                }
            }
        }
    }
}
$\endgroup$
  • $\begingroup$ Do you want a systematic construction, or would computer-generated codes be good? $\endgroup$ – joriki Mar 6 '16 at 15:27
  • $\begingroup$ @joriki A systematic construction would be interesting, of course, but just having the codes themselves would be quite all right. $\endgroup$ – Théophile Mar 6 '16 at 15:58
  • $\begingroup$ I tried to construct some with simulated annealing, but didn't get very far. Have you considered leveraging the binary codes? A threefold variation of your $5$-bit code with $20$ words yields a code with $5$ ternary digits and $60$ words: $$ $$ 000000011100011111110000000222000222222211111112221112222222 000111000111111100000002220002222222111111122211122222220000 110001111111000000022200022222221111111222111222222200000001 011111110000000222000222222211111112221112222222000000011100 111100000002220002222222111111122211122222220000000111000111 $\endgroup$ – joriki Mar 6 '16 at 21:09
  • $\begingroup$ That's not great, though, considering it could have up to $243$ words. What sort of word count are you aiming for? $\endgroup$ – joriki Mar 6 '16 at 21:12
  • $\begingroup$ Ah, nice. I hadn't thought of doing that. I'm actually interested in relatively short codes, i.e., big enough to be non-trivial but small enough to not be overwhelming to a human, if that makes sense. A good size for $n=3$ or $n=4$ would be around $20$ or $30$ words, for example. $\endgroup$ – Théophile Mar 7 '16 at 1:52
2
+100
$\begingroup$

Your $5$-bit example suggests a semi-systematic computer-aided construction. All we need for constructing this code is the first four words; the rest follows by repeating them in cyclically shifted form. The conditions are that each successive step contains only one digit change; that the step from the last word to the first contains one digit change and a cyclical shift; and that none of the words are cyclically shifted versions of each other or themselves. This latter condition implies that none of the words are periodic, which slightly limits the maximal number of words.

Here's code that constructs such sequences of words. Below are maximal codes it finds for $k=3$ and $3\le n\le6$. In view of the exclusion of periodic words, the maximal number of words is $k^n-k$ for the prime numbers $3$ and $5$ (i.e. $24$ and $240$, respectively), $k^4-k^2=81-9=72$ for $n=4$ and $k^6-k^3-k^2+k=729-27-9+3=696$ for $n=6$, so these codes are maximal with respect to this construction. The code also outputs codes with fewer words; if you want shorter ones, you can run it yourself or let me know the target word counts and I'll run it for you.

$n=3\,\,:\,\,3\cdot8=24$ words

00222221
01120000
11111022

$n=4\,\,:\,\,4\cdot18=72$ words

022200022222221100
001110000220000000
111111221111022110
000111111122222222

$n=5\,\,:\,\,5\cdot48=240$ words

110011110001222222222222222211111111110000000222
111111100011122111100000000000222111111000001111
222000000000000002111200021110012222222222222221
211111111222222211110000111000000011000011222200
222220111111112222222220000000000001122221122222

$n=6\,\,:\,\,6\cdot116=696$ words

00000000000000000000222000002222222211111111221111111112222222211111111111111111111100000000000000002222222211111111
22000222222211122211111111222222222222222100000000000000000111111000022222211111110000000000221112222200000002222200
00011112222221110000011112222200001111200002222112222222111111111100000111112222200000001100000211111111110000002222
22222222112222222221111111111222200002222222200000220000000012222222222222111111111111222221111111111111100111122220
22222222222222111111110000011110000000000000000000011111120000000002221122222002111111111000022222000002111111222222
12221100022111111000000011111111000222220000000022222011111111221111000002222211111002200000000000011222222222222000
$\endgroup$
  • 1
    $\begingroup$ This is great! Thank you very much for your work. $\endgroup$ – Théophile Mar 7 '16 at 16:36
  • $\begingroup$ @Théophile: You're welcome. One more thing: It may be possible to insert periodic words into these sequences -- e.g. in the $n=4$ code, 0000 could be added at the very beginning, and 1111 could be added between 2111 and 0111; in the $n=3$ code 111 could be added between 011 and 211. If you were looking for maximal codes, the Java code could be augmented to systematically create opportunities for such insertions. $\endgroup$ – joriki Mar 7 '16 at 18:53
0
$\begingroup$

I came back to this problem and wrote some code myself: it turns out that a basic backtracking algorithm works very effectively. The following is in Ruby and takes these parameters:

augment(pos, len, code, radix, num_tracks, offsets, cover)

pos: the position of the next bit (this should start at 0)
len: length of the desired code  
code: the Gray code itself; this should be initialized to an array of nil  
radix: the base of the code (e.g., for binary code, choose 2)  
num_tracks: number of tracks   
offsets: offsets of tracks   
cover: records whether a given value has been generated by the code

For example, to get a $30$-word single-track binary code $5$-bit words, and with each track offset by $3$ from the last:

augment(0, 30, [nil]*30, 2, 5, [0,3,6,9,12], {})

000000001111100111111110000011
011000000001111100111111110000
000011000000001111100111111110
110000011000000001111100111111
111110000011000000001111100111

The Ruby code:

DISPLAY_PROGRESS = true

def print_code(code, radix, num_tracks, offsets)
    (0...num_tracks).each do |track|
        print " " * 10
        (0...code.length).each do |i|
            print code[(i - offsets[track]) % code.length].to_s.center(3)
        end
        print "\n"
    end
    print " " * 10, "-" * code.length * 3, "\n"
    print " " * 10
    (0...code.length).each do |i|
        total_value = 0
        (0...num_tracks).each do |t|
            track_value = code[(i - offsets[t]) % code.length]
            if track_value == nil || total_value == nil
                total_value = nil
            else
                total_value += (radix ** t) * track_value
            end
        end
        if total_value == nil then total_value = "-" end
        print total_value.to_s.center(3)
    end
end

def augment(pos, code, radix, num_tracks, offsets, cover)
    if DISPLAY_PROGRESS then print " " * pos, ".\n" end
    #if (rand(1000) == 0) then print "." end

    if pos == code.length   # hooray! got to the end
        print "\n" * 2, "- " * 30, "S U C C E S S ", "- " * 30, "\n" * 2
        print_code(code, radix, num_tracks, offsets)
        print "\n" * 3
        exit
    end

    if code[pos] != nil
        print "Error?\n"
        exit
    end

    [*0...radix].shuffle.each do |i|
        code[pos] = i
        total_value = Array.new(num_tracks){ 0 }
        collision = 0
        (0...num_tracks).each do |track|    # changing the code in one place effectively changes it in num_track places; check to see if there are collisions
            changed_bits = 0    # also see how many bits were changed from preceding word; if more than 1, then consider this a "collision" also
            (0...num_tracks).each do |t|
                track_value = code[(pos + offsets[track] - offsets[t]) % code.length]
                if track_value == nil || total_value[track] == nil
                    total_value[track] = nil
                else
                    total_value[track] += (radix ** t) * track_value
                end

                previous_track_value = code[(pos + offsets[track] - offsets[t]) % code.length - 1]
                if previous_track_value != nil || track_value != nil
                    if previous_track_value != track_value then
                        changed_bits += 1
                        if changed_bits > 1 then collision = 1 end
                    end
                end
            end

            if total_value[track] != nil && cover[total_value[track]] == 1
                collision = 1
            end
        end

        if (total_value - [nil]).uniq.size < (total_value - [nil]).size
            collision = 1
        end

        if collision == 0
            (0...num_tracks).each do |track|
                if total_value[track] != nil then cover[total_value[track]] = 1 end
            end
            augment(pos + 1, code, radix, num_tracks, offsets, cover)

            # if code gets here, we're backtracking
            (0...num_tracks).each do |track|
                if total_value[track] != nil then cover[total_value[track]] = 0 end
            end

            if DISPLAY_PROGRESS then print "x" * pos, "/\n" end
        end
    end

    code[pos] = nil
end

len = 30
code = Array.new(len){ nil }
radix = 2
num_tracks = 5
offsets = [0, 3, 6, 9, 12]
cover = {}

print "\n"
augment(0, code, radix, num_tracks, offsets, cover)
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.