Python permutations with constraints

Question

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.

For instance, I have a list L=[1, 2, 3, 4, 5, 6, 7]

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

• 1 should always come before 2.
• 3 should come before 4 which in turn should come before 5.
• Finally, 6 should come before 7.

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

Answer 1

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]

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.

Answer 2

def partial_permutations(*groups):
    groups = list(filter(None, groups)) # remove empties.
    # Since we iterate over 'groups' twice, we need to
    # make an explicit copy for 3.x for this approach to work.
    if not groups:
        yield []
        return
    for group in groups:
        for pp in partial_permutations(*(
             g[1:] if g == group else g
             for g in groups
        )):
            yield [group[0]] + pp