具有特定顺序的笛卡尔积

Question

我需要按特定顺序输出 N 个列表的笛卡尔积。

我知道如何按“默认”顺序构建产品：

给定集合 (a, b, c), (x, y), (1, 2, 3)，首先我生成 ax1，然后迭代最后一个集合以获得 ax2、ax3，然后更改第二个集合中的元素并迭代ay1、ay2、ay3 等……

在生成 N-1 个元素的产品之前，我需要的顺序不应该是任何集合中的第 N 个元素

期望的结果是 ax1, ax2, ay1, ay2, bx1, bx2, by1, by2, ax3, ay3, bx3, by3, cx1, cx2, cx3, cy1, cy2, cy3。看，在生成具有第二个元素的所有产品之前，我没有得到 ax3（包含 (1, 2, 3) 中的第三个元素）。

我目前的算法是：

trunace 设置为长度 1
生成产品
截断集长度2
生成产品
删除重复项，保留顺序
...
截断集长度max length of all sets
生成产品
删除重复项，保留顺序

每一步“生成产品”也会生成上一步的所有产品，所以我必须删除它们

它是获得所需订单的更好算法吗？它有名字吗？

Answer 1

不确定此订单是否有名称，但这似乎可以满足您的要求，而无需删除重复的项目。

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)]
)))

具有特定顺序的笛卡尔积

Cartesian product with specific order

algorithm

combinatorics

cartesian-product