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.
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]
下一篇: 迭代适合特定键的排列