时间戳

首页 > 解决方案 > 具有特定顺序的笛卡尔积

algorithm - 具有特定顺序的笛卡尔积

问题描述

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

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

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

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

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

我目前的算法是：

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

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

标签： algorithmcombinatoricscartesian-product

解决方案

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

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

推荐阅读