python之向排列添加约束

我正在尝试计算 list = [0,1,2,3,4,5,6] 遵守某些约束的所有排列。

• 位置 0 必须 > 3
• 位置 3 + 位置 5 <位置 4< li>

在我当前的代码中，我确定了每个排列和迭代的所有排列和迭代，并应用了约束。

import itertools 
 
Used_permutations = []     
numbers = [0,1,2,3,4,5,6] 
all_permutations = list(itertools.permutations(numbers)) #Determine all permutations 
 
for permutation in all_permutations: 
    if permutation[0] > 3 and permutation[3] + permutation[5] < permutation[4]: #Constraints applied to permutations 
        Used_permutations.append(permutation)   
        #################################################### 
        ###   Apply calculations to current permutation ### 
        #################################################### 

此代码的问题在于，我浪费时间寻找所有可能的排列，只是为了再次过滤掉它们。有人可以在确定排列时协助应用约束的方法，所以不是所有 N!确定了吗？

请您参考如下方法:

而不是先创建一个 list所有排列，然后将其中一些元素添加到第二个列表并丢弃其余元素(在本例中约为 90%)，您可以使用列表理解来过滤 itertools 产生的排列在创建时。

>>> numbers = [0,1,2,3,4,5,6] 
>>> [p for p in itertools.permutations(numbers) if p[0] > 3 and p[3] + p[5] < p[4]] 
[(4, 0, 1, 2, 6, 3, 5), 
 (4, 0, 1, 3, 6, 2, 5), 
 ... a few more ... 
 (6, 5, 4, 1, 3, 0, 2), 
 (6, 5, 4, 2, 3, 0, 1)] 
>>> len(_) 
516 

如果检查变得更加复杂，您甚至不必使用列表理解。您可以在常规 for 中执行相同操作用 if 循环条件，唯一的区别是您没有收集 list 中的所有排列首先，但直接迭代生成器:

all_permutations = itertools.permutations(numbers)  # no list(...) 
for permutation in all_permutations: 
    ... 

这两种方法仍然生成所有的 N!排列，但大多数会立即被丢弃，只有“正确”的排列才会存储在列表中。

如果您甚至不想生成它们，则必须实现自定义递归 permutations算法并手动检查是否对于 p[3] 的给定值p[5] 可以有任何有效值等等。像这样:

def manual_permutations(numbers, n=0, last=0, lastlast=0): 
    if len(numbers) <= 1: 
        yield tuple(numbers) 
    else: 
        for i, first in enumerate(numbers): 
            # first constraint 
            if n == 0 and first <= 3: continue 
            # second constraint: 3 + 5 < 4 === 3 - 4 < -5 === 3 < 4 - 5 
            # assuming numbers are ordered: rest[0] is min, rest[-1] is max 
            rest = numbers[:i] + numbers[i+1:] 
            if n == 3 and first >= rest[-1] - rest[0]: continue 
            if n == 4 and last - first >= - rest[0]: continue 
            if n == 5 and lastlast - last >= - first: continue 
            # constraints okay, recurse 
            for perm in manual_permutations(rest, n+1, first, last): 
                yield (first,) + perm 

这会在生成排列时检查两个约束，因此如果例如所有以数字 <= 3 开头的排列根本不会生成。第二个检查有点复杂，可能会进一步改进(如果我们在函数的开头添加一个计数器，我们会看到大约有 1200 次递归调用)。无论如何，使用 IPython 的 %timeit我们看到，“手动”方法的动态检查仍然比使用 itertools 慢三倍 ，因此即使改进检查也可能不会比这更快。^*)此外，您自己的原始循环实际上也没有那么慢。

>>> %timeit original_loop(numbers) 
1000 loops, best of 3: 736 µs per loop 
 
>>> %timeit list(itertools_perms(numbers)) 
1000 loops, best of 3: 672 µs per loop 
 
>>> %timeit list(manual_permutations(numbers)) 
100 loops, best of 3: 2.11 ms per loop 

当然，根据输入列表的大小和约束条件，手动方法可以或多或少地节省一些费用，但也可能(或多或少)难以实现或适应不断变化的约束条件。就个人而言，我仍然会使用 itertools.permutations以及一些简单易读的过滤器。

^*) 更新:在我之前的编辑中，手动方法更快；这是因为我忘记了实际使用这两个函数返回的生成器。