15
\$\begingroup\$

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 , so the shortest code in bytes wins
\$\endgroup\$
18
  • \$\begingroup\$ Sandbox \$\endgroup\$
    – pxeger
    Mar 9 at 6:44
  • \$\begingroup\$ Very closely related \$\endgroup\$
    – Bubbler
    Mar 9 at 6:47
  • \$\begingroup\$ Is the output required to start with 0...0? \$\endgroup\$
    – alephalpha
    Mar 9 at 6:58
  • \$\begingroup\$ Can we output all possibilities? \$\endgroup\$
    – emanresu A
    Mar 9 at 7:04
  • 1
    \$\begingroup\$ @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. \$\endgroup\$
    – Neil
    Mar 9 at 9:56

10 Answers 10

10
\$\begingroup\$

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
}
\$\endgroup\$
6
\$\begingroup\$

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.
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Is _:fTl a sufficient condition for being a valid Gray code? \$\endgroup\$
    – pxeger
    Mar 9 at 7:34
  • 2
    \$\begingroup\$ @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. \$\endgroup\$ Mar 9 at 7:55
6
\$\begingroup\$

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
\$\endgroup\$
5
\$\begingroup\$

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.

\$\endgroup\$
5
\$\begingroup\$

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)
\$\endgroup\$
4
\$\begingroup\$

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()
\$\endgroup\$
2
\$\begingroup\$

Charcoal, 30 29 28 bytes

NθNηIEXθηE÷ιXθ⮌…⁰η⌊﹪⟦⊖±λλ⟧⊗θ

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:

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

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.

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
0

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.