CODEWITHSUNDEEP
pythonalgorithmpermutationpython-itertools
DoubleBass
DoubleBass

Reputation: 1173

Iterating through permutations that fit a specific key

Imagine some list

L = [(1,2,3),(4,5,6),(7,8),(9,10),(11,12,13)]

I want to iterate through all permutations of this list that fit an arbitrary length key such as (2,2,3,3,3).

So in this case, all permutations where the length of the elements fits that key.

[(7,8),(9,10),(1,2,3),(4,5,6),(11,12,13)]

[(9,10),(7,8),(1,2,3),(4,5,6),(11,12,13)]

[(7,8),(9,10),(4,5,6),(1,2,3),(11,12,13)]

etc.

Right now I am just iterating through all permutations and only taking the ones that fit the key, but this goes through a lot of wasted time and permutations. I'd much rather generate what I need directly but I don't know how to do it at all, despite looking into itertools more deeply.

Upvotes: 1

Views: 61

Answers (1)

Sven Marnach
Sven Marnach

Reputation: 601599

You can build the permutations of the tuples of different lengths spearately and combine them:

from itertools import chain, permutations, product
tuples_by_length = {}
for t in L:
    tuples_by_length.setdefault(len(t), []).append(t)
for x, y in product(permutations(tuples_by_length[2]),
                    permutations(tuples_by_length[3])):
    print list(chain(x, y))

Output:

[(7, 8), (9, 10), (1, 2, 3), (4, 5, 6), (11, 12, 13)]
[(7, 8), (9, 10), (1, 2, 3), (11, 12, 13), (4, 5, 6)]
[(7, 8), (9, 10), (4, 5, 6), (1, 2, 3), (11, 12, 13)]
[(7, 8), (9, 10), (4, 5, 6), (11, 12, 13), (1, 2, 3)]
[(7, 8), (9, 10), (11, 12, 13), (1, 2, 3), (4, 5, 6)]
[(7, 8), (9, 10), (11, 12, 13), (4, 5, 6), (1, 2, 3)]
[(9, 10), (7, 8), (1, 2, 3), (4, 5, 6), (11, 12, 13)]
[(9, 10), (7, 8), (1, 2, 3), (11, 12, 13), (4, 5, 6)]
[(9, 10), (7, 8), (4, 5, 6), (1, 2, 3), (11, 12, 13)]
[(9, 10), (7, 8), (4, 5, 6), (11, 12, 13), (1, 2, 3)]
[(9, 10), (7, 8), (11, 12, 13), (1, 2, 3), (4, 5, 6)]
[(9, 10), (7, 8), (11, 12, 13), (4, 5, 6), (1, 2, 3)]

This approach can be generalised to arbitrary length keys:

def permutations_with_length_key(lst, length_key):
    tuples_by_length = {}
    for t in L:
        tuples_by_length.setdefault(len(t), []).append(t)
    positions = {k: i for i, k in enumerate(tuples_by_length.iterkeys())}
    for x in product(*[permutations(v) for v in tuples_by_length.itervalues()]):
        x = map(iter, x)
        yield [next(x[positions[y]]) for y in length_key]

Upvotes: 4

Related Questions