为排列添加约束条件

Question

为排列添加约束条件

3

我正在尝试计算列表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!个排列？

- Pierre

1

同时，位置0大于3意味着位置0是4，因为4是唯一满足条件的候选数。 - Ma0

假设您所说的第3、4和5个位置是指第2、3和4个位置，那么只有四种排列满足您的条件。 [4, 2, 0, 3, 1]，[4, 2, 1, 3, 0]，[4, 3, 0, 2, 1]和[4, 3, 1, 2, 0]。 - Ma0

忘记了这两个[4, 1, 0, 3, 2]和[4, 1, 2, 3, 0]。所以一共有6个。 - Ma0

抱歉，复制了错误的列表。请编辑以更正列表。 - Pierre

@Pierre 现在太晚了，伙计。 - Ma0

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- tobias_k · Accepted Answer

与其首先创建所有排列的列表，然后将其中一些元素添加到第二个列表中并丢弃其余部分（在这种情况下约为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和一些简单易懂的过滤器。

^*)更新：在我的先前编辑中，手动方法更快；这是因为我忘记了实际上消耗由两个函数返回的生成器。