添加约束到排列

Question

我试图用list = [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%),您可以使用列表推导来过滤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一些简单易读的过滤器.

^*)更新:在我之前的编辑中,手动方法出现得更快; 这是因为我忘了实际使用这两个函数返回的生成器.