Gray code on N symbols

Question

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

Task

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 code-golf, so the shortest code in bytes wins

Answer 1

BQN, 12 bytes^SBCS

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
}

Answer 2

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.

Answer 3

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

Answer 4

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.

Answer 5

05AB1E, 11 10 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.

Try it online or verify all test cases.

Original 11 10 bytes answer:

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)

Answer 6

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 /
                           //   NB: we should start with s = 0, but since
                           //       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()

Answer 7

Charcoal, 30 29 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

Answer 8

Haskell, 59 bytes

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(`mod`n).(zipWith(-)<*>(0:))<$>mapM(\_->[1..n])[1..k]

Try it online!

The part left of <$> can be either zipWith(((`mod`n).).(-))<*>(0:) or zipWith(\a b->mod(a-b)n)<*>(0:) at no byte difference.

Answer 9

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!

Answer 10

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\$.