递归生成 + 过滤。更好的非递归方法？

1 投票

3 回答

885 浏览

提问于 2025-04-15 13:37

我有以下需求（用Python实现）：

生成所有可能的长度为12的元组（也可以更长），这些元组的元素只能是0、1或2（基本上就是一个12位的三进制数）
根据特定标准过滤这些元组，去掉不符合要求的，保留我需要的。

之前我处理的元组长度都比较小，所以用函数式编程的方法很简单：一个递归函数生成所有可能的元组，然后用过滤函数去掉不需要的部分。现在因为长度变大，生成这些元组的时间变得很长，远超出我的预期，因为在解决方案的树状结构中，大部分路径最后都会被去掉，所以我可以跳过它们的创建。

我有两个解决方案：

把生成过程改成循环，并在每生成一个新的12位元组时就应用过滤标准
把过滤过程整合进递归算法中，这样可以避免进入那些注定会被去掉的路径。

我更倾向于第一个方案（看起来更简单），但我想听听大家的意见，特别是从函数式编程的角度来看，这种情况应该怎么处理。

过滤递归函数式编程算法效率组合优化元组生成三进制数循环算法

3 个回答

我会实现一个迭代的二进制加法器或者汉明码，然后以这种方式运行。

回答于 2025-04-15 由 Python大师

分享举报

itertools 是一个可以帮助我们处理这类问题的工具。不过，这里有一种（硬编码的）方法，可以使用生成器来解决这个问题：

T = (0,1,2)

GEN = ((a,b,c,d,e,f,g,h,i,j,k,l) for a in T for b in T for c in T for d in T for e in T for f in T for g in T for h in T for i in T for j in T for k in T for l in T)

for VAL in GEN:
    # Filter VAL
    print VAL

回答于 2025-04-15 由 Python大师

分享举报

怎么样呢

import itertools

results = []
for x in itertools.product(range(3), repeat=12):
    if myfilter(x):
        results.append(x)

这里的 myfilter 是用来筛选的。比如说，这里只允许结果中有10个或更多的1，

def myfilter(x):  # example filter, only take lists with 10 or more 1s
    return x.count(1)>=10

也就是说，我的建议是你的第一种选择。在某些情况下，这种方法可能会比较慢，因为（根据你的标准）你可能会生成很多不需要的列表，但它更通用，而且编写起来非常简单。

补充：这种方法也可以用一行代码来实现，就像评论里hughdbrown提到的那样：

results = [x for x in itertools.product(range(3), repeat=12) if myfilter(x)]

回答于 2025-04-15 由 Python大师

分享举报

递归生成 + 过滤。更好的非递归方法？

3 个回答

撰写回答