如何创建无集合意义重复的笛卡尔积迭代器？

你遇到的核心问题是：普通笛卡尔积会生成大量集合意义上重复的元组（比如(1,2)和(2,1)），而你之前的筛选方法需要把所有已生成的元组存在列表里，当repeat参数变大时，内存会直接爆炸。其实我们可以换个思路——直接生成不会产生集合重复的元组，完全不需要存储历史数据，用迭代器按需生成。

最优解决方案：使用itertools.combinations_with_replacement #

Python的itertools库已经内置了combinations_with_replacement函数，它生成的是元素非递减排列的元组，这意味着每个无序集合只会对应唯一的一个元组，从根源上避免了集合重复。而且它本身就是迭代器，不会一次性把所有元素加载到内存，完美解决内存问题。

示例代码 #

import itertools
A = list(range(1, 10))
# 第二个参数对应你原来的repeat值，比如repeat=2就传2
iterator = itertools.combinations_with_replacement(A, 2)
print(list(iterator))

输出结果会是：

[(1,1), (1,2), (1,3), ..., (8,9), (9,9)]

你会发现完全没有(2,1)、(3,1)这类集合重复的元组，而且整个过程是按需生成元素，哪怕repeat设为10，也不会占用大量内存。

为什么这个方法有效？ #

combinations_with_replacement的设计目标就是生成“允许元素重复，但不考虑顺序”的组合。它生成的元组始终满足a1 ≤ a2 ≤ ... ≤ ak（k是你传入的第二个参数，对应原来的repeat），这样每个无序集合（比如{1,2}）只会被表示为(1,2)这一种形式，不会出现排列后的重复项。

对比你之前的方法：

• 你的筛选方法时间复杂度是O(n^{k)（n是集合大小，k是repeat值），内存占用也是O(n}k)，当k较大时完全不可行；
• combinations_with_replacement的时间复杂度是O(C(n+k-1, k))（组合数），远小于笛卡尔积的规模，内存占用仅为O(1)（迭代器每次只生成一个元素）。

处理不可比较元素的情况 #

如果你的集合元素不是可比较的（比如字符串、自定义对象等），可以通过索引映射的方式实现：

import itertools
A = ["apple", "banana", "cherry"]
indices = range(len(A))

def unique_set_product(iterable, repeat):
    for idx_tuple in itertools.combinations_with_replacement(indices, repeat):
        yield tuple(iterable[i] for i in idx_tuple)

iterator = unique_set_product(A, 2)
print(list(iterator))

输出结果：

[('apple', 'apple'), ('apple', 'banana'), ('apple', 'cherry'), ('banana', 'banana'), ('banana', 'cherry'), ('cherry', 'cherry')]

同样满足集合无重复的需求，且内存友好。

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