将约束添加到排列中

Question

我试图计算列表=[0,1,2,3,4,5,6]遵循一些约束的所有置换。在

• 位置0必须大于等于3
• 位置3+位置5<；位置4

在我当前的代码中，我通过应用约束来确定所有的置换和迭代。在

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！有决心吗？在

Answer 1

您不必先创建所有排列的list，然后将其中的一些元素添加到第二个列表中并丢弃其余的元素（在本例中约为90%），您可以使用列表理解来过滤由{}生成的置换。在

>>> 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中的所有置换，而是直接迭代生成器：

^{pr2}$

这两种方法仍然会产生所有的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慢3倍，所以即使改进检查也不会使其更快。^*）而且，实际上，您自己的原始循环也没有那么慢。在

>>> %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和一些简单易读的过滤器。在

---

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