为排列添加约束 [英] Adding constraints to permutations

问题描述

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

I am trying to calculate all permutations with list = [0,1,2,3,4,5,6] adhering to some constraints.

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

在当前代码下，我应用约束来确定每个排列的所有排列和迭代.

With my current code I determining all permutations and iterations through each, applying the constraints.

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！确定吗?

The problem with this code is that I'm wasting time finding all possible permutations just to filter them out again. Can someone assist with a way to apply the constraints while permutations are determined so not all N! are determined?

推荐答案

而不是先创建所有排列的list，然后将其中一些元素添加到第二个列表中，然后丢弃其余元素(在此列表中约占90％)情况)，您可以使用列表推导过滤itertools在创建时产生的排列.

Instead of first creating a list of all the permutations and then adding some of those elements to a second list and discarding the rest (about 90% in this case), you can use a list comprehension to filter the permutations yielded by itertools as they are created.

>>> 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

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

If the checks become more complicated, you do not even have to use a list comprehension. You can do the same in a regular for loop with if conditions, the only difference being that you do not collect all the permutations in a list first, but iterate the generator directly:

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

这两种方法仍会在所有N个条件下产生！排列，但大多数排列会立即被丢弃，并且只有正确的"排列被存储在列表中.

Both approaches will still generate all the N! permutations, but most are immediately discarded and only the "right" ones are ever stored in the list.

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

If you do not even want to generate them, you will have to implement a custom recursive permutations algorithm and manually check whether e.g. for a given value for p[3] there can be any valid values for p[5] and so on. Something like this:

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慢 三倍，因此即使改进检查也可能不会使其更快. ^*)而且，实际上，您自己的原始循环也没有那么慢.

This checks the two constraints while generating the permutations, so that if e.g. all the permutations starting with a number <= 3 are not generated at all. The second check is a bit more complicated, and could probably be improved further (if we add a counter to the beginning of the function, we see that there are ~1200 recursive calls). Anyway, using IPython's %timeit we see that the "manual" approach with checks on the fly is still about three times slower than using itertools, so even improving the checks will probably not make it faster than that.^*) Also, your own original loop is, in fact, not that much slower, either.

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

Of course, depending on the size of the input list and the constraints, the manual approach can present more or less of a saving, but can also be (much) more or less difficult to implement or to adapt to changing constraints. Personally, I'd still go with using itertools.permutations and a few simple, readable filters.

^*)更新:在我之前的编辑中，手动方法更快地出现了.这是因为我忘记了消耗这两个函数返回的生成器.

^*) Update: In my previous edit, the manual approach came out faster; this was because I forgot to actually consume the generators returned by the two functions.

这篇关于为排列添加约束的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！