# Gray code on N symbols

A Gray code is a permutation on binary numbers where incrementing or decrementing a number only ever causes a single bit to change. For example, a Gray code for the binary numbers up to 7 (so, with 3 bits) are:

000
001
011
010
110
111
101
100


You can see that only one bit is different between each consecutive pair.

This is only one valid 3-bit Gray code; others are possible by permuting the columns or reversing the list.

An $$\ N \$$-ary Gray Code is a generalised Gray code which operates on $$\ N \$$ symbols instead of just two. For example, a Gray code with $$\ N = 3 \$$, and of length 2:

00
01
02
12
11
10
20
21
22


Note that a single digit can change up or down by more than one from one step to the next. For example, the following is allowed: (as a partial output for $$\ N = 4 \$$, $$\ k = 3 \$$)

001
003


Here is another possible output, which is also allowed:

21
22
20
00
10
11
01
02
12


Given two integers, $$\ N \$$ and $$\ k \$$, output an $$\ N \$$-ary Gray code of length $$\ k \$$.

You may output using any consistent set of $$\ N \$$ distinct symbols; they don't necessarily have to be digits or integers.

You may assume both $$\ N \ge 2 \$$ and $$\ k \ge 2 \$$.

There are multiple orderings for all inputs; you only need to output at least one of these, but you may output multiple.

## Test cases

I list only one possible output for each.

N  k  output
2  2  00, 01, 11, 10
3  2  00, 01, 02, 12, 11, 10, 20, 21, 22
2  3  000, 001, 011, 010, 110, 111, 101, 100
5  2  00, 01, 02, 03, 04, 14, 10, 11, 12, 13, 23, 24, 20, 21, 22, 32, 33, 34, 30, 31, 41, 42, 43, 44, 40
4  4  0000, 0001, 0002, 0003, 0013, 0010, 0011, 0012, 0022, 0023, 0020, 0021, 0031, 0032, 0033, 0030, 0130, 0131, 0132, 0133, 0103, 0100, 0101, 0102, 0112, 0113, 0110, 0111, 0121, 0122, 0123, 0120, 0220, 0221, 0222, 0223, 0233, 0230, 0231, 0232, 0202, 0203, 0200, 0201, 0211, 0212, 0213, 0210, 0310, 0311, 0312, 0313, 0323, 0320, 0321, 0322, 0332, 0333, 0330, 0331, 0301, 0302, 0303, 0300, 1300, 1301, 1302, 1303, 1313, 1310, 1311, 1312, 1322, 1323, 1320, 1321, 1331, 1332, 1333, 1330, 1030, 1031, 1032, 1033, 1003, 1000, 1001, 1002, 1012, 1013, 1010, 1011, 1021, 1022, 1023, 1020, 1120, 1121, 1122, 1123, 1133, 1130, 1131, 1132, 1102, 1103, 1100, 1101, 1111, 1112, 1113, 1110, 1210, 1211, 1212, 1213, 1223, 1220, 1221, 1222, 1232, 1233, 1230, 1231, 1201, 1202, 1203, 1200, 2200, 2201, 2202, 2203, 2213, 2210, 2211, 2212, 2222, 2223, 2220, 2221, 2231, 2232, 2233, 2230, 2330, 2331, 2332, 2333, 2303, 2300, 2301, 2302, 2312, 2313, 2310, 2311, 2321, 2322, 2323, 2320, 2020, 2021, 2022, 2023, 2033, 2030, 2031, 2032, 2002, 2003, 2000, 2001, 2011, 2012, 2013, 2010, 2110, 2111, 2112, 2113, 2123, 2120, 2121, 2122, 2132, 2133, 2130, 2131, 2101, 2102, 2103, 2100, 3100, 3101, 3102, 3103, 3113, 3110, 3111, 3112, 3122, 3123, 3120, 3121, 3131, 3132, 3133, 3130, 3230, 3231, 3232, 3233, 3203, 3200, 3201, 3202, 3212, 3213, 3210, 3211, 3221, 3222, 3223, 3220, 3320, 3321, 3322, 3323, 3333, 3330, 3331, 3332, 3302, 3303, 3300, 3301, 3311, 3312, 3313, 3310, 3010, 3011, 3012, 3013, 3023, 3020, 3021, 3022, 3032, 3033, 3030, 3031, 3001, 3002, 3003, 3000
11 2  0 0, 0 1, 0 2, 0 3, 0 4, 0 5, 0 6, 0 7, 0 8, 0 9, 0 10, 1 10, 1 0, 1 1, 1 2, 1 3, 1 4, 1 5, 1 6, 1 7, 1 8, 1 9, 2 9, 2 10, 2 0, 2 1, 2 2, 2 3, 2 4, 2 5, 2 6, 2 7, 2 8, 3 8, 3 9, 3 10, 3 0, 3 1, 3 2, 3 3, 3 4, 3 5, 3 6, 3 7, 4 7, 4 8, 4 9, 4 10, 4 0, 4 1, 4 2, 4 3, 4 4, 4 5, 4 6, 5 6, 5 7, 5 8, 5 9, 5 10, 5 0, 5 1, 5 2, 5 3, 5 4, 5 5, 6 5, 6 6, 6 7, 6 8, 6 9, 6 10, 6 0, 6 1, 6 2, 6 3, 6 4, 7 4, 7 5, 7 6, 7 7, 7 8, 7 9, 7 10, 7 0, 7 1, 7 2, 7 3, 8 3, 8 4, 8 5, 8 6, 8 7, 8 8, 8 9, 8 10, 8 0, 8 1, 8 2, 9 2, 9 3, 9 4, 9 5, 9 6, 9 7, 9 8, 9 9, 9 10, 9 0, 9 1, 10 1, 10 2, 10 3, 10 4, 10 5, 10 6, 10 7, 10 8, 10 9, 10 10, 10 0


## Rules

• You may use any standard I/O method
• For compactness in the test-cases, when $$\ N \le 10 \$$, I've squished the output digits together. However, your output format must always have an unambiguous separation of the digits when $$\ N > 10 \$$
• Standard loopholes are forbidden
• This is , so the shortest code in bytes wins
• Sandbox Commented Mar 9, 2022 at 6:44
• Very closely related Commented Mar 9, 2022 at 6:47
• Is the output required to start with 0...0? Commented Mar 9, 2022 at 6:58
• Can we output all possibilities? Commented Mar 9, 2022 at 7:04
• @KevinCruijssen Actually I understood his question has having an entirely different meaning, i.e. is it allowed to start the code on any k digits, not just all 0s.
– Neil
Commented Mar 9, 2022 at 9:56

# BQN, 12 bytesSBCS

Based on an algorithm given on Wikipedia. Takes k as left and N as right argument.

⊢|-⟜»¨∘⥊∘↕∘⥊


Run online!

⥊∘↕∘⥊ Generate a list of all base-N numbers of length k.
Then each number is transformed to Gray code, lets look at an example:

N=3, k=3, number is 2 1 2
-⟜»                   # Shift a 0 into the number and subtract that from the number.
2 1 2 - 0 2 1 → 2 ¯1 1
⊢|                    # modulo N; This relies on Python-like modulo, otherwise you might need to add N before
3 | 2 ¯1 1    → 2 2 1


Slightly ungolfed:

{k 𝕊 n:
n|{𝕩-»𝕩}¨⥊↕k⥊n
}


# Vyxal, 10 bytes

ʁÞẊṖ'¯:fTl


Try it Online!

   Ṗ'      # Find all permutations of...
ÞẊ        # Cartesian power of input and...
ʁ          # Range(input)
'      # Where...
¯     # Differences (vectorising)
:  l # Length is unchanged when...
fT  # Flattening and getting truthy indices.

• Is _:fTl a sufficient condition for being a valid Gray code? Commented Mar 9, 2022 at 7:34
• @pxeger For it to accept a change of multiple symbols there would also have to be a change of no symbols, but the words should be unique already. Commented Mar 9, 2022 at 7:55

# Jelly, 6 bytes

ṗ@Ż€I%


A dyadic Link that accepts the length, $$\k\$$, on the left and the number of symbols, $$\N\$$ on the right and yields a list of lists of non-negative integers.

Try it online!

### How?

This is the same cyclic Gray code that the algorithm displayed on Wikipedia will produce (for values $$\[1,N^k]+[0]\$$) with each result reversed.

ṗ@Ż€I% - Link: k, N
@     - with swapped arguments:
ṗ      -   [1..N] Cartesian product [1..k]
Ż€   - prefix a zero to each
I  - incremental differences
% - modulo N


# Wolfram Language (Mathematica), 45 bytes

Mod[#-{0,##&@@Most@#}&/@Range@#~Tuples~#2,#]&


Try it online!

A port of @ovs's BQN answer.

# Wolfram Language (Mathematica), 59 bytes

IntegerDigits[FindHamiltonianPath@GridGraph@Table@##-1,##]&


Try it online!

Finds a Hamiltonian path of the $$\\underbrace{N\times\cdots\times N}_{k}\$$ grid graph.

# 05AB1E, 1110 9 bytes

LIãε0š¥¹%


-1 byte porting @ovs' BQN answer, using the approach described on Wikipedia.

Inputs in the order $$\N,k\$$. Outputs a single result using 0-based integers in the range $$\[0,N)\$$, like the challenge description.

LIãœʒü-ĀOP


Inputs in the order $$\N,k\$$. Outputs using 1-based integers in the range $$\[1,N]\$$, and will output all possible results (and is very slow because of that).

Try it online or verify some of the smaller test cases (with the filter ʒ replaced with a find_first .Δ to speed things up a bit).

Explanation:

L           # Push a list in the range [1, first (implicit) input N]
Iã         # Get the second input k's cartesian product of this list
ε        # Map over each inner k-tuple:
0š      #  Prepend a 0
¥     #  Pop and push the deltas/forward-differences
¹%   #  Modulo-N on each value
# (after which the list of lists is output implicitly as result)

LIã         # Same as above
œ        # Get all possible permutations of these k-tuples
ʒ       # Filter this list of permutations by:
ü      #  For each overlapping k-tuple:
-     #   Subtract the values at the same positions in the tuples
Ā    #  Check for each that it's NOT 0 (0 if 0; 1 otherwise)
O   #  Sum to get the amount of values that differ per overlapping pair
P  #  Get the product of these sums
#  (only 1 is truthy in 05AB1E, so only the permutations where each
#  overlapping k-tuple has a single value different are kept)
# (after which the filtered list of k-tuple permutations is output
# implicitly as result)


# JavaScript (ES7),  82  78 bytes

Expects (N)(k).

N=>k=>[...Array(N**k)].map(g=(s=i=k,v)=>i--?[x=~~(s+v/N**i)%N,...g(s-x,v)]:[])


Try it online!

### Commented

This is based on the algorithm given on Wikipedia.

N =>                       // N = number of symbols
k =>                       // k = code length
[...Array(N ** k)]         // build an array of N ** k entries
.map(g = (                 // g is a recursive callback function taking:
s =                    //   s = step     \__ initially set to k
i = k,                 //   i = position /
//       we're working modulo N, it actually
//       doesn't matter
v                      //   v = current value in [0 .. N ** k - 1]
) =>                     //
i-- ?                    //   decrement i; if it was not 0:
[                      //     update the output:
x =                  //       define x as:
~~(s + v / N ** i) //         floor(s + v / N ** i)
% N,               //         modulo N
...g(s - x, v)       //       append the result of a recursive call
//       with s - x and v unchanged
]                      //     end of output update
:                        //   else:
[]                     //     stop the recursion
)                          // end of map()


# Charcoal, 3029 28 bytes

ＮθＮηＩＥＸθηＥ÷ιＸθ⮌…⁰η⌊﹪⟦⊖±λλ⟧⊗θ


Try it online! Link is to verbose version of code. Outputs each digit of the gray code as a base 10 number on its own line, with each gray code double-spaced from the next. Explanation:

Ｎθ                              Input N as a number
Ｎη                            Input k as a number
θ                        Input N
Ｘ                         To the power of
η                       Input k
Ｅ                          Map over implicit range
ι                    Current value
÷                     Vectorised integer divide
θ                  Input N
Ｘ                   Vectorised to power
…                Range from
⁰               Literal integer 0
η              To input k
⮌                 Reversed
Ｅ                      Map over list
λ        Current value
±         Negated
⊖          Decremented
⟦    ⟧      List of that and
λ       Current value
﹪            Vectorised modulo
θ    Input N
⊗     Doubled
⌊             Take the minimum
Ｉ                           Cast to string
Implicitly print


Uses [1..N] for the digits.

n!0=[[]]
n!k=[a:x|a<-[1..n],x<-iterate reverse(n!(k-1))!!a]


Try it online!

This uses a simple recursive construction: Given the Gray code for k-1, alternate between this and its reverse for each of the new digits. iterate reverse x !! a reverses x for odd a (and can probably be shortened). The approach is described in more detail on Wikipedia.

The other approach is a byte longer:

n!k=map(modn).(zipWith(-)<*>(0:))<$>mapM(\_->[1..n])[1..k]  Try it online! The part left of <$> can be either zipWith(((modn).).(-))<*>(0:) or zipWith(\a b->mod(a-b)n)<*>(0:) at no byte difference.

# Perl 5, 94 bytes

sub g{($N,$k)=@_;--$k?do{@a=g($N,$k);map{//;map[$',@$_],@a=reverse@a}0..$N-1}:map[$_],0..$N-1}


Try it online!

# C (gcc), 163 $$\\cdots\$$ 149 146 bytes

s;w;i;p;*f(n,k){int*g=calloc(p=pow(n,k),4*k),b[p*k];for(;p--;){for(w=p,i=0;s=w;w/=n)b[p*k+i++]=w%n;for(;i--;s+=n-g[w])g[w]=(b[w=p*k+i]+s)%n;}s=g;}


Try it online!

Saved 3 bytes thanks to ceilingcat!!!

Inputs two integers $$\N\$$ and $$\k\$$.
Returns a pointer to a (flattened) $$\N\$$-ary Gray code of length $$\k\$$.