Give me the Gray Code list of bit width n

Question

The Gray Code is a sequence of binary numbers of bitwidth n where successive numbers differ only in one bit (see example output).

Reference

Example input:

3

Example output:

000
001
011
010
110
111
101
100

Notes:

• This question seems to have a dupe but it's not, for that question is not a code-golf, and it demands different output. It will help to check out it's answers, though.
• You may assume a variable n which contains the input.

Answer 1

J, 24 bytes

[:#:@/:2|2+/\"1@#:@i.@^]

Try it online!

Different algorithm that converts \$1..2^n\$ to regular binary, scan sums each of the binary digits, mods by 2, takes the grade up, and converts back to binary.

This works because scan summing the digits returns the inverse grey code sequence - A006068, and grade up is self-inverse.

J, 24 bytes

[:#:@(22 b.<.@-:)[:i.2^]

Try it online!

Straightforward implementation of the "XOR with it's own floored half" algorithm. Note that 22 b. is XOR.

Answer 2

JavaScript (77)

for(i=0;i<1<<n;)alert((Array(n*n).join(0)+(i>>1^i++).toString(2)).substr(-n))

More browser-friendly version (console.log and prompt()):

n=prompt();for(i=0;i<1<<n;)console.log((Array(n*n).join(0)+(i>>1^i++).toString(2)).substr(-n))

Answer 3

Ruby — 42 39

Same algorithm, different language:

(2**n).times{|b|puts"%0#{n}b"%(b>>1^b)}

Switching from #map to #times as @voidpigeon suggests saves 3 characters.

Answer 4

Japt, 14 12 bytes

2pU Ç^z)¤ùTU

Shaved off two bytes thanks to ETHproductions.

Try it online!

Answer 5

K (ngn/k), 25 bytes

{(x-1){,/0 1,''|:\x}/0 1}

Try it online!

---

• |:\xis "reverse scan x". applies reverse to x until the output equals the input, and shows each iteration. returns (0 1; 1 0) on first pass.
• 0 1,'' is "0 1 join each each". joins a 0 to each value of 1st elem, and 1 to each value of 2nd elem, giving ((0 0; 0 1);(1 1; 1 0)) on first pass
• ,/ is "join over", and flattens to list.
• (x-1){...}/0 1is "apply {func} over 0 1 x-1 times". takes the output of the last iteration as input

Answer 6

Python 3, 48 bytes

for i in range(1<<n):print(bin(2**n+i//2^i)[3:])

Explanation:

• The outer loop iterates over numbers from 0 to 2^n - 1
• For each number i, the expression bin(2**n + i//2 ^ i) calculates the Gray code:
  • 2^n is added to i//2, effectively shifting i one position to the right
  • The XOR operator ^ is used to perform the Gray code transformation
  • Adding 2^n ensures the resulting binary representation has n bits
  • bin() converts the integer to a binary string
  • [3:] slices the binary string to remove the prefix '0b', leaving only the n-bit Gray code

Ungolfed:

n = int(input())  # Take input for the number of bits in the Gray code

for i in range(1 << n): # Iterate over numbers from 0 to 2^n - 1
    gray_code = bin(2**n + i // 2 ^ i) # Calculate the Gray code for the current number
    print(gray_code[3:]) # Print the Gray code excluding the prefix '0b'

Try it online!

Answer 7

Python 2 (47)

for i in range(2**n):print bin(2**n+i/2^i)[3:]

The expression i/2^i for the i'th gray code number is from the this answer. To add leading zeroes that pad to length n, I add 2**n before converting to a binary string, creating a string of length n+1. Then, I truncate the leading 1 and number type prefix 0b with [3:].

Answer 8

K (ngn/k), 10 bytes

+~0=':!n#2

Try it online!

Answer 9

APL (Dyalog Classic), 11 bytes

2≠/0,↑,⍳n⍴2

Try it online!

n⍴2 is 2 2...2 - a vector of n twos

⍳ is the indices of an n-dimensional array with shape 2 2...2 - that is, a 2×2×...×2 array of nested vectors. As we use 0-indexing (⎕IO←0), those are all binary vectors of length n.

, flatten the 2×2×...×2 shape, so we get a vector of 2ⁿ nested binary vectors

↑ "mix" - convert the vector of vectors to a solid 2ⁿ×n matrix. It looks like this:

0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1

0, prepends zeroes to the left of the matrix

2≠/ computes the pairwise (2) xor (≠) along the last dimension (/ as opposed to ⌿); in other words, every element gets xor-ed with its right neighbour, and the last column disappears

0 0 0
0 0 1
0 1 1
0 1 0
1 1 0
1 1 1
1 0 1
1 0 0

Answer 10

Python - 54

Based off of an algorithm from the reference given in the challenge:

for i in range(2**n):print'{1:0{0}b}'.format(n,i>>1^i)

Ungolfed:

# For each of the possible 2**n numbers...
for num in range(2**n):
    gray = num>>1 ^ num
    
    # Print in binary and pad with n zeros.
    print '{1:0{0}b}'.format(grey)

Answer 11

PowerShell(168)

Amateur PowerShell'r back with another attempt at golF! Hope you don't mind! At the very least these questions are fun, and a learning experience to boot. Assuming n has been inputted, we have:

$x=@('0','1');for($a=1;$a-lt$n;$a++){$x+=$x[($x.length-1)..0];$i=[Math]::Floor(($x.length-1)/2);0..$i|%{$x[$_]='0'+$x[$_]};($i+1)..($x.length-1)|%{$x[$_]='1'+$x[$_]}}$x

Because the PowerShell I'm working with is only 2.0, I can't use any bit shifting cmdlets which might make for shorter code. So I took advantage of a different method described in the question source, flipping the array and adding it to itself, appending a 0 to the front of the top half, and a 1 to the bottom half.

Answer 12

APL (22)

{(0,⍵)⍪1,⊖⍵}⍣(n-1)⍪0 1

This outputs a n-by-2^n matrix containing the bits as its rows:

      n←3
      {(0,⍵)⍪1,⊖⍵}⍣(n-1)⍪0 1
0 0 0
0 0 1
0 1 1
0 1 0
1 1 0
1 1 1
1 0 1
1 0 0

Explanation:

• {...}⍣(n-1)⍪0 1: run the function n-1 times with initial input the matrix (0 1)T (which is the 1-bit gray code)

  • (0,⍵): each row of ⍵ with a 0 prefixed,
  • ⍪: on top of,
  • 1,⊖⍵: each row of ⍵ with an 1 prefixed, in reversed order

Answer 13

F# (86) (84) (80)

for i in 0..(1<<<n)-1 do printfn"%s"(Convert.ToString(i^^^i/2,2).PadLeft(n,'0'))

This could probably be improved further.

Also note, if run in FSI, you'd need to open System;; first. If you'd like to avoid importing that, (and if you don't care about the order in which the values are printed) you can use this 82-character version:

for i in 0..(1<<<n)-1 do(for j in 0..n-1 do printf"%i"((i^^^i/2>>>j)%2));printfn""

Answer 14

Jq 1.5, 105 100 bytes

def g(n):if n<2then. else map([0]+.)+(reverse|map([1]+.))|g(n-1)end;[[0],[1]]|g(N)[]|map("\(.)")|add

Assumes N provides input. e.g.

def N: 3 ;

Expanded

def g(n):  # recursively compute gray code
  if n < 2
  then .
  else map([0]+.) + (reverse|map([1]+.)) | g(n-1)
  end;

  [[0],[1]]                 # initial state
| g(N)[]                    # for each element in array of gray codes
| map("\(.)")|add           # covert to a string

Try it online!

Answer 15

MATL, 10 bytes

W:qt2/kZ~B

Try it online!

The good old "XOR n with n>>2" method.

W - compute 2^(input) (gets input implicitly)
:q - create range of numbers from 0 to 2^n - 1
t - duplicate that range
2/k - MATL doesn't have bitshift, so divide (each number) by 2 and floor
Z~ - elementwise XOR that result with the original 0 to 2^n - 1 array
B - convert each number in the result to binary
(Implicitly display output.)

Answer 16

J, 14 bytes

#:(,#+|.)^:n 0

Try it online!

A snippet assuming variable n as specified in the challenge.

A Gray code of order n can be constructed from order n-1 by the following steps:

• Take two copies of the previous one.
• Reverse the second.
• Prepend 0 bit to the first and 1 to the second.

As a list of integer values, prepending the 1 bit corresponds to adding 2^(n-1), which is precisely the length of the previous Gray code, and prepending 0 is a no-op. Therefore, one such iteration can be summarized to "append length plus reverse to self", which is what (,#+|.) does.

#:(,#+|.)^:n 0
  (     )^:n 0    Starting from a single 0, repeat n times:
      |.            Reverse
    #+              Add length to each item
   ,                Append to self
                  (0 -> 0 1 -> 0 1 3 2 -> 0 1 3 2 6 7 5 4 -> ...)
#:                Convert each number to binary

J, 17 bytes

[:#:(,#+|.)@[&0&0

Try it online!

Same solution as a function. @[&0&0 part is a bit tricky:

f@[&0&0
f          A monadic(1-arg) function
 @[        Convert to a dyadic(2-arg) function that uses the left arg,
           ignoring the right
   &0      Attach a dummy argument on the right side to get a "bind" function
     &0    Treat a "bind" function as dyadic, where left arg becomes
           repetition count and right arg is the starting value,
           and set 0 as the starting value

Answer 17

Japt, 10 bytes

³Ç¤ÅÃf_Ê¥U

Try it online!

Answer 18

Scala 3, 102 bytes

Golfed version. Attempt This Online!

for(i<-0 to scala.math.pow(2,n).toInt-1)println((scala.math.pow(2,n).toInt+i/2^i).toBinaryString.tail)

Ungolfed version. Attempt This Online!

object Main {
  def main(args: Array[String]): Unit = {
    val n = 3
    for (i <- 0 until scala.math.pow(2, n).toInt) {
      val result = (scala.math.pow(2, n).toInt + i / 2 ^ i).toBinaryString
      println(result.drop(1))
    }
  }
}

Answer 19

Perl 5 + -a, 38 bytes

printf"%0@{F}b
",$_^$_/2for 0..2**$_-1

Try it online!

Explanation

I originally hoped to solve this using globs but the ordering was the hard part. In the end I opted for the approach defined on the OEIS article.

for each n from 0 to two to the power of n ($_) minus one printf the 0 padded (to a length of @F, which is the list of input which, in this case, is only one number and so interpolates correctly into the format string) binary representation of the next number in the gray sequence (n XOR n/2), followed by a newline.

Answer 20

APL(NARS), 31 chars

{2∣↑+/(⍵⍴2)∘⊤¨¨(⌊m÷2)m←¯1+⍳2*⍵}

I hope this generate gray code. It is something as {toBinary¨{⍵ xor ⌊⍵÷2}¨0..¯1+2*⍵}. Test:

  f←{2∣↑+/(⍵⍴2)∘⊤¨¨(⌊m÷2)m←¯1+⍳2*⍵}
  f 2
0 0  0 1  1 1  1 0 
  f 3
0 0 0  0 0 1  0 1 1  0 1 0  1 1 0  1 1 1  1 0 1  1 0 0 
  f 4
0 0 0 0  0 0 0 1  0 0 1 1  0 0 1 0  0 1 1 0  0 1 1 1  0 1 0 1  0 1 0 0  1 1 0 0  1 1 0 1  1 1 1 1  1 1 1 0  1 0 1 0  1 0 1 1  1 0 0 1  1 0 0 0 

Answer 21

T-SQL 134

This challenge is asking to return the Cartesian power of {(0),(1)}. This snippet builds the code which would execute the Cartesian product of {(0),(1)} n times.

DECLARE @ int=4,@s varchar(max)='SELECT*FROM's:set @s+='(VALUES(0),(1))t'+ltrim(@)+'(b)'if @>1set @s+=','set @-=1if @>0goto s exec(@s)