有约束的Python排列 [英] Python permutations with constraints

问题描述

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

I am using python 3 and I am trying to find a way to get all the permutations of a list while enforcing some constraints.

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

我想找到所有排列.但是，我的约束是:

I want to find all permutations. However, My constraints are:

• 1应该始终排在2之前.
• 3应该排在4之前，反过来又应该排在5之前.
• 最后，应该在7之前是6.

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

Of course, I can generate all permutations and ignore those which do not follow these constraints but this wouldn't be efficient I guess.

推荐答案

此方法使用简单的过滤器过滤排列.

This approach filters permutations using a simple filter.

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]

我们在这里所做的是找到多集置换. (在这种情况下，多重集为groupdxs.)这是论文，其中详细介绍了此算法的O(1)算法.

What we are doing here is finding permutations of a multiset. (In this case the multiset is groupdxs.) Here's a paper that details an O(1) algorithm for this.

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