finding ternary single-track Gray codes

Question

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;
                }
            }
        }
    }
}

Answer 1

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