Cartesian product in Gray code order with itertools?

user_2489449 0
Viewed 106

Is there something like Python's itertools.product() that provides the iteration through the Cartesian product of a set of sets in Gray code order? For example, supposing that such a hypothetical generator existed, and it was called gray_code_product(), then gray_code_product(['a','b','c'], [0,1], ['x','y']) would generate, in the order :

('a',0,'x')
('a',0,'y')
('a',1,'y')
('a',1,'x')
('b',1,'x')
('b',1,'y')
('b',0,'y')
('b',0,'x')
('c',0,'x')
('c',0,'y')
('c',1,'y')
('c',1,'x')
gray-code itertools product python
1 Answers

According to the documentation of itertools.product, the function is equivalent to the following Python code:

def product(*args, repeat=1):
    pools = [tuple(pool) for pool in args] * repeat
    result = [[]]
    for pool in pools:
        result = [x+[y] for x in result for y in pool]
    for prod in result:
        yield tuple(prod)

Since a gray code product is about reversing the order of the preceding sequence for each pool, you can use enumerate on the previous result list while iterating over it to determine if the index is odd or even-numbered, and reverse the sequence of the pool if it's odd-numbered:

def gray_code_product(*args, repeat=1):
    pools = [tuple(pool) for pool in args] * repeat
    result = [[]]
    for pool in pools:
        result = [x+[y] for i, x in enumerate(result) for y in (
            reversed(pool) if i % 2 else pool)]
    for prod in result:
        yield tuple(prod)

so that:

for p in gray_code_product(['a','b','c'], [0,1], ['x','y']):
    print(p)

outputs:

('a', 0, 'x')
('a', 0, 'y')
('a', 1, 'y')
('a', 1, 'x')
('b', 1, 'x')
('b', 1, 'y')
('b', 0, 'y')
('b', 0, 'x')
('c', 0, 'x')
('c', 0, 'y')
('c', 1, 'y')
('c', 1, 'x')
user_68909120
Related