如何在不实际创建 $n$ 次幂集的情况下搜索集合的 $n$ 次幂中的元素？

Question

有一个给定的集合 S。我想从 $S^n$ 中搜索元素（ $S$ 与其本身 $n$ 次的笛卡尔积）验证某些属性。但我不想 实际创建 $S^n$ 因为它占用空间。

例如搜索符合条件的元素 在$S^3$中，我可以写

for x in S:
  for y in S:
    for z in S:
      if P(x,y,z): print (x,y,z)

但是我写代码的时候$n$没有被修复，我无法使用上面的方法。有没有办法 优雅地做到这一点？ （如果相关的话我使用Python）谢谢！

Answer 1

您可以编写一个函数来生成所需幂集的成员：

def powerset(s,n):
    if n==1:
        ys = [[]] 
    else:
        ys = powerset(s,n-1)
    for y in ys: 
        for x in s:
            yield [x]+y 

>> list(powerset([1,2,3],3))

[[1, 1, 1], [2, 1, 1], [3, 1, 1], [1, 2, 1], [2, 2, 1], [3, 2, 1], [1, 3, 1], [2, 3, 1], [3, 3, 1], [1, 1, 2], [2, 1, 2], [3, 1, 2], [1, 2, 2], [2, 2, 2], [3, 2, 2], [1, 3, 2], [2, 3, 2], [3, 3, 2], [1, 1, 3], [2, 1, 3], [3, 1, 3], [1, 2, 3], [2, 2, 3], [3, 2, 3], [1, 3, 3], [2, 3, 3], [3, 3, 3]]