Python中如何快速对大量排列变体执行多条件校验筛选有效项

原代码的性能瓶颈来源于海量的无效遍历：当act=6时，单组全排列共6! = 720种，prop=3的情况下总遍历量达到720^3 = 3.7亿+，且所有校验逻辑都在生成完整变体后才执行，大量算力浪费在不符合基础条件的无效变体上。核心优化思路是把过滤条件前置到生成环节，通过剪枝砍掉无效路径，从源头减少计算量，具体实现如下：

具体优化手段 #

• 提前过滤单排列硬约束：把仅和单个排列相关的固定条件先做过滤，直接缩小可选排列的范围
  • 原逻辑中this_variant[0][1] == 1：直接过滤掉所有第1位不是1的排列0，可选量从720降到5! = 120
  • 原逻辑中this_variant[1][4] == 0：直接过滤掉所有第4位不是0的排列1，可选量降到120
  • 原逻辑中this_variant[2][0] == 4：直接过滤掉所有第0位不是4的排列2，可选量降到120
    仅这一步就可以把总遍历量从3.7亿降到120*120*120 = 172.8万，性能直接提升200倍以上
• 逐层校验关联约束：不要等三个排列都生成完再校验，每生成一层排列就校验当前可判断的关联条件，不符合直接跳过后续层级的排列生成
• 优化慢操作：原代码中list.index()是O(n)操作，预存索引值避免重复计算，进一步节省时间

优化后代码示例 #

from itertools import permutations
from datetime import datetime

timerstart = datetime.now()

# 预生成符合单约束的排列，提前存好需要复用的属性
valid_perm0 = [p for p in permutations(range(6)) if p[1] == 1]
# 生成排列1时直接存好3的索引，避免循环中重复调用index
valid_perm1 = [(p, p.index(3)) for p in permutations(range(6)) if p[4] == 0]
valid_perm2 = [p for p in permutations(range(6)) if p[0] == 4]

for p0 in valid_perm0:
    p0_0, p0_4 = p0[0], p0[4]
    for p1, p1_3index in valid_perm1:
        # 不满足p0和p1的关联条件直接跳过，不需要再遍历p2
        if p1_3index != p0_0:
            continue
        p1_3 = p1[3]
        for p2 in valid_perm2:
            # 校验剩余关联条件
            if p2[2] != p1_3 or p2[4] != p0_4:
                continue
            # 其余n个校验条件可以依次往下加
            print('valid: ', (p0, p1, p2))
            # 已知只有1个有效结果，找到直接跳出所有循环
            break
        else:
            continue
        break
    else:
        continue
    break

timerend = datetime.now()
print('it took: {} seconds'.format((timerend-timerstart).seconds))

如果约束条件更多，剪枝效果会更明显，绝大多数场景下可以做到秒级出结果。

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