带约束的 Python 排列

Question

我正在使用 python 3，我正在尝试找到一种方法来获取列表的所有排列，同时强制执行一些约束。

例如，我有一个列表 L=[1, 2, 3, 4, 5, 6, 7]

我想找到所有排列。但是，我的限制是:

• 1 应该总是在 2 之前。
• 3 应该在 4 之前，而 4 又应该在 5 之前。
• 最后，6 应该在 7 之前。

当然，我可以生成所有排列并忽略那些不遵循这些约束的排列，但我想这效率不高。

Answer 1

这种方法使用简单的过滤器过滤排列。

import itertools

groups = [(1,2),(3,4,5),(6,7)]
groupdxs = [i for i, group in enumerate(groups) for j in range(len(group))]
old_combo = []
for dx_combo in itertools.permutations(groupdxs):
    if dx_combo <= old_combo: # as simple filter
        continue
    old_combo = dx_combo
    iters = [iter(group) for group in groups]
    print [next(iters[i]) for i in dx_combo]

我们在这里做的是寻找 permutations of a multiset . (在这种情况下，多重集是 groupdxs。)这是一个 paper详细说明了 O(1) 算法。