CODEWITHSUNDEEP
pythonpython-3.xlistpermutationrepeat
S. Avenci
S. Avenci

Reputation: 23

Efficient Permutation of a Sorted List with Repetitions

I have a list of names assigned to ranks, often with ranks duplicated. I want to generate all permutations of the list with keeping the ranks in sorted order. For example:

[Sam(17), Harry(17), Bob(5), Sally(5)]

would generate

Sam(17), Harry(17), Bob(5), Sally(5)

Sam(17), Harry(17), Sally(5), Bob(5)

Harry(17), Sam(17), Bob(5), Sally(5)

Harry(17), Sam(17), Sally(5), Bob(5)

Essentially, for every distinct group of ranks, there are n! combinations. In this case it would be 2! * 2!. I'm having trouble finding an efficient way to do permutations for a list with 34 names across 8 ranks.

I'm running out of memory trying to find 2! * 2! * 4! * 2! * 2! *8! * 4! * 10! different lists.

Is there any efficient way to generate this list? How much memory would python need?

Upvotes: 0

Views: 197

Answers (1)

Paul Panzer
Paul Panzer

Reputation: 53029

Here is an itertools solution using groupby, permutations and product. As it mostly uses generators it should be not too heavy on memory. If you don't need the result as a list, but for example just want to iterate over it memory requirements should in fact be rather modest.

If you need the list, you'll need the memory for the list but not much more.

But I'm afraid with your numbers the final list alone will just be too large to fit in memory. And the loop will take forever.

>> import itertools, operator
>>> 
>>> data = *zip('Peter Paul Mary Jack Jill'.split(), (17, 17, 17, 4, 4)),
>>> data
(('Peter', 17), ('Paul', 17), ('Mary', 17), ('Jack', 4), ('Jill', 4))
>>> 
# group by rank
>>> groups = itertools.groupby(data, operator.itemgetter(1))
# extract the groups and generate all permutations of each of them
>>> permutations = map(itertools.permutations, map(operator.itemgetter(1), groups))
# form the cartesian product of the permutations, flatten out excess nesting
# convert inner generators to lists
>>> result = map(list, map(itertools.chain.from_iterable, itertools.product(*permutations)))
>>> for i in result:
...     print(i)
... 
[('Peter', 17), ('Paul', 17), ('Mary', 17), ('Jack', 4), ('Jill', 4)]
[('Peter', 17), ('Paul', 17), ('Mary', 17), ('Jill', 4), ('Jack', 4)]
[('Peter', 17), ('Mary', 17), ('Paul', 17), ('Jack', 4), ('Jill', 4)]
[('Peter', 17), ('Mary', 17), ('Paul', 17), ('Jill', 4), ('Jack', 4)]
[('Paul', 17), ('Peter', 17), ('Mary', 17), ('Jack', 4), ('Jill', 4)]
[('Paul', 17), ('Peter', 17), ('Mary', 17), ('Jill', 4), ('Jack', 4)]
[('Paul', 17), ('Mary', 17), ('Peter', 17), ('Jack', 4), ('Jill', 4)]
[('Paul', 17), ('Mary', 17), ('Peter', 17), ('Jill', 4), ('Jack', 4)]
[('Mary', 17), ('Peter', 17), ('Paul', 17), ('Jack', 4), ('Jill', 4)]
[('Mary', 17), ('Peter', 17), ('Paul', 17), ('Jill', 4), ('Jack', 4)]
[('Mary', 17), ('Paul', 17), ('Peter', 17), ('Jack', 4), ('Jill', 4)]
[('Mary', 17), ('Paul', 17), ('Peter', 17), ('Jill', 4), ('Jack', 4)]

Upvotes: 1

Related Questions