Python Challenges: Generate list with 'width'-bit gray code

Last update on December 21 2024 07:49:49 (UTC/GMT +8 hours)

From Wikipedia,
The reflected binary code (RBC), also known just as reflected binary (RB) or Gray code after Frank Gray, is an ordering of the binary numeral system such that two successive values differ in only one bit (binary digit). The reflected binary code was originally designed to prevent spurious output from electromechanical switches. Today, Gray codes are widely used to facilitate error correction in digital communications such as digital terrestrial television and some cable TV systems.

Write a Python program to generate list with 'width'-bit gray code.

Sample Solution:

Python Code:

def binaryString(n,w=0):
    """
    Ref.: https://bit.ly/3cWJD22
    return binary representation of 'n' as a 'w'-width string.
    
    >>> binaryString(6)
    '110'
    >>> binaryString(3,4)
    '0011'
    """

    from collections import deque
    bits = deque()
    while n > 0:
        bits.appendleft(('0','1')[n&1])
        n >>= 1
    while len(bits) < w:
        bits.appendleft('0')
    return ''.join(bits)

def gray(width):
    """return list with 'width'-bit gray code.

    >>> gray(1)
    ['0', '1']
    >>> gray(2)
    ['00', '01', '11', '10']
    >>> gray(3)
    ['000', '001', '011', '010', '110', '111', '101', '100']
    """

    return [binaryString(n ^ (n>>1),width) for n in range(2**width)]


print(gray(2))
print("\n",gray(3))
print("\n",gray(4))

Sample Output:

['00', '01', '11', '10']

 ['000', '001', '011', '010', '110', '111', '101', '100']

 ['0000', '0001', '0011', '0010', '0110', '0111', '0101', '0100', '1100', '1101', '1111', '1110', '1010', '1011', '1001', '1000']

Flowchart:

Python Code Editor:

Contribute your code and comments through Disqus.

Previous: Write a Python program to print a truth table for an infix logical expression.
Next: Write a Python program to get a dictionary mapping keys to huffman codes for a frequency table mapping keys to frequencies.