Cartesian product with specific order

Question

I need to output cartesian product of N lists in specific order.

I know how to build products in "default" order:

Given sets (a, b, c), (x, y), (1, 2, 3), first I produce ax1, then iterate over last set to get ax2, ax3, then change element in the second set and iterate over the last set again for ay1, ay2, ay3, etc...

The order I need should not go for the N-th element in any set, before producing products of N-1 elements

Desired result is ax1, ax2, ay1, ay2, bx1, bx2, by1, by2, ax3, ay3, bx3, by3, cx1, cx2, cx3, cy1, cy2, cy3. See, I don't get ax3 (containing 3rd element from (1, 2, 3)), before producing all products with 2nd elements.

My current algorithm is:

• trunace sets to length 1
• generate products
• truncate sets to length 2
• generate products
• remove duplicates, preserving order
• ...
• truncate sets to length max length of all sets
• generate products
• remove duplicates, preserving order

Each step "generate products" also generates all products from the previous step, so I have to remove them

Is it the better algorith to get desired order? Does it have a name?

Answer 1

Not sure if this order has a name, but this seems to do what you ask for without having to remove repeated items.

from itertools import islice, product, zip_longest

def specific_order_cartesian(lists):
    its = [[lst[0]] for lst in lists]
    yield tuple(lst[0] for lst in lists)

    for column in list(islice(zip_longest(*lists), 1, None)):
        for i, p in reversed(list(enumerate(column))):
            if p is None:
                continue

            yield from product(
                *(
                    (p,) if j == i else its[j]
                    for j in range(len(lists))
                )
            )

            its[i].append(p)


print(list(specific_order_cartesian(
    [('a', 'b', 'c',), ('x', 'y'), (1, 2, 3)]
)))