python - 使所有元组的 1 不超过 0

Question

例如，我可以制作仅包含 1 和 0 的所有 n 元组 A= list(itertools.product([0, 1], repeat=n))。如何在不A先创建然后删除大量元组的情况下有效地制作所有 1 不超过 0 的元组？

Answer 1

在将它们保留在列表中之前，即时删除它们。

A = [x for x in itertools.product([0, 1], repeat=n) if sum(x)*2<=n]

我怀疑生成它们是整个算法的“难”部分。所以不用担心生成不必要的一半元组和更多 1 的 2 倍开销。

此外，请记住，对于较大的 N，该列表将占用大量内存。也许您可以一直使用生成器。

记录：我的第一次尝试仅适用于 python 2.x，因为 3.x itertools.ifilter() 只是变成了 filter()。

A = list(itertools.ifilter(
          lambda x:sum(x)*2<=n, 
          itertools.product([0, 1], repeat=n)))

Answer 2

def generate(Tuple, n):
    if len(Tuple) == n:
        print Tuple
    else:   
        if Tuple.count(1) >= n / 2:     # If number of 1 is greater then n/2
            generate(Tuple + (0, ), n)  # then we can't append 1 to the tuple
        else:
            generate(Tuple + (1, ), n)
            generate(Tuple + (0, ), n)

if __name__ == '__main__':      
    n = 4
    generate((), n)