如何在不生成集合n次笛卡尔积的情况下搜索符合条件的元素（Python）

Python里直接用标准库itertools的product函数就能优雅解决这个问题，它完美适配n不固定的场景，而且是惰性生成的——不会一次性把整个$S^n$的元素都加载到内存里，和你写嵌套循环的空间效率完全一致。

代码示例 #

假设你的集合S是[1,2,3]，n是3，判断条件P是“三个数之和大于5”，代码可以这么写：

import itertools

S = [1, 2, 3]
n = 3

def P(x, y, z):
    return x + y + z > 5

# 遍历笛卡尔积的每个元素（惰性生成，不占额外空间）
for item in itertools.product(S, repeat=n):
    if P(*item):
        print(item)

如果你的判断函数P的参数是元组形式（比如直接接收(x,y,z)），那不用解包，直接传item就行：

def P(tuple_item):
    return sum(tuple_item) > 5

for item in itertools.product(S, repeat=n):
    if P(item):
        print(item)

为什么这个方法好用 #

• 不管n是多少，只需要改repeat参数的值，不用修改循环结构
• 迭代器模式，每次只生成一个元素，内存占用极低，完全符合你“不想实际生成$S^n$”的需求
• 标准库实现，经过优化，性能比自己写递归或嵌套循环更稳定

如果你不想用标准库（自己实现） #

也可以写一个递归生成器来模拟笛卡尔积的惰性生成，比如：

def cartesian_product(S, n):
    if n == 1:
        for elem in S:
            yield (elem,)
    else:
        for elem in S:
            for sub_tuple in cartesian_product(S, n-1):
                yield (elem,) + sub_tuple

# 使用方式和itertools.product一致
for item in cartesian_product(S, n):
    if P(*item):
        print(item)

不过除非有特殊需求，还是优先用itertools.product，毕竟是官方维护的高效实现。

内容的提问来源于stack exchange，提问作者Jiu