Source code for ec_gen.gray_code

"""
Gray Code Generator

This code implements a Gray code generator, which is a sequence of binary
numbers where each successive number differs from the previous one by only one
bit. The code consists of two main functions: brgc_gen and brgc.

The brgc_gen function generates a sequence of numbers representing which bit
to flip in order to create the Gray code sequence. It takes an integer n
as input, which represents the number of bits in the binary code. The
function uses a recursive approach to generate the sequence. For example,
if n is 4, it will produce a sequence like
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0. Each number
in this sequence indicates which bit position to flip to get the next Gray
code.

The brgc function uses the sequence generated by brgc_gen to create the
actual Gray code. It also takes an integer n as input, representing the
number of bits. It starts with a list of n zeros and then flips
the bits according to the sequence from brgc_gen. The function yields
each step of the Gray code sequence as a list of 0s and 1s.

The code achieves its purpose by using a clever recursive algorithm for
brgc_gen. For n bits, it first generates the sequence for n-1 bits,
then yields n-1 (to flip the nth bit), and then generates the n-1
sequence again. This creates a mirrored pattern that ensures each
successive number differs by only one bit.

An important aspect of the code is how it transforms the bit-flipping
sequence into the actual Gray code. The brgc function maintains a list
of bits and flips them one at a time based on the output of brgc_gen.
This transformation is what converts the simple sequence of numbers into a
valid Gray code.

The code also includes examples in the docstrings, showing how to use
these functions. One example demonstrates printing the Gray code sequence
using black and white square characters, which helps visualize the
changing bits in the sequence.
"""

from typing import Generator




def brgc_gen(n: int) -> Generator[int, None, None]:
    """
    The function `brgc_gen` generates a sequence of binary reflected gray
    code numbers up to a given length `n`.

    :param n: The parameter `n` represents the number of bits in the
              binary reflected gray code sequence
    :type n: int
    :return: The function `brgc_gen` returns a generator object.

    Examples:
        >>> for i in brgc_gen(4):
        ...     print(f"flip {i}")
        ...
        flip 0
        flip 1
        flip 0
        flip 2
        flip 0
        flip 1
        flip 0
        flip 3
        flip 0
        flip 1
        flip 0
        flip 2
        flip 0
        flip 1
        flip 0
    """
    if n == 1:
        yield 0
        return
    yield from brgc_gen(n - 1)
    yield n - 1
    yield from brgc_gen(n - 1)





def brgc(n: int) -> Generator[list[int], None, None]:
    """
    The function `brgc` generates a binary reflected gray code sequence of
    length `n`.

    :param n: The parameter `n` represents the number of bits in the
              binary code
    :type n: int

    Examples:
        >>> s = "◾◽"
        >>> for lst in brgc(4):
        ...     mylst = list(s[i] for i in lst)
        ...     print("".join(mylst))
        ...
        ◾◾◾◾
        ◽◾◾◾
        ◽◽◾◾
        ◾◽◾◾
        ◾◽◽◾
        ◽◽◽◾
        ◽◾◽◾
        ◾◾◽◾
        ◾◾◽◽
        ◽◾◽◽
        ◽◽◽◽
        ◾◽◽◽
        ◾◽◾◽
        ◽◽◾◽
        ◽◾◾◽
        ◾◾◾◽
    """
    bits = list(0 for _ in range(n))
    yield bits
    for idx in brgc_gen(n):
        bits[idx] = 1 - bits[idx]  # flip
        yield bits



if __name__ == "__main__":
    import doctest

    doctest.testmod()