How to generate permutations of a list without "reverse duplicates" in Python using generators
This is related to question How to generate all permutations of a list in Python
How to generate all permutations that match following criteria: if two permutations are reverse of each other (i.e. [1,2,3,4] and [4,3,2,1]), they are considered equal and only one of them should be in final result.
Example:
permutations_without_duplicates ([1,2,3])
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
I am permuting lists that contain unique integers.
The number of resulting permutations will be high so I'd like to use Python's generators if possible.
Edit: I'd like not to store list of all permutations to memory if possible.
I have a marvelous followup to SilentGhost's proposal - posting a separate answer since the margins of a comment would be too narrow to contain code :-)
itertools.permutations
is built in (since 2.6) and fast. We just need a filtering condition that for every (perm, perm[::-1]) would accept exactly one of them. Since the OP says items are always distinct, we can just compare any 2 elements:
for p in itertools.permutations(range(3)):
if p[0] <= p[-1]:
print(p)
which prints:
(0, 1, 2)
(0, 2, 1)
(1, 0, 2)
This works because reversing the permutation would always flip the relation between first and last element!
For 4 or more elements, other element pairs that are symmetric around the middle (e.g. second from each side p[1] <= p[::-1][1]
) would work too.
(This answer previously claimed p[0] < p[1]
would work but it doesn't — after p is reversed this picks different elements.)
You can also do direct lexicographic comparison on whole permutation vs it's reverse:
for p in itertools.permutations(range(3)):
if p <= p[::-1]:
print(p)
I'm not sure if there is any more effecient way to filter. itertools.permutations
guarantees lexicographic order, but the lexicographic position p
and p[::-1]
are related in a quite complex way. In particular, just stopping at the middle doesn't work.
But I suspect (didn't check) that the built-in iterator with 2:1 filtering would outperform any custom implementation. And of course it wins on simplicity!
If you generate permutations in lexicographical order, then you don't need to store anything to work out whether the reverse of a given permutation has already been seen. You just have to lexicographically compare it to its reverse - if it's smaller then return it, if it's larger then skip it.
There's probably a more efficient way to do it, but this is simple and has the properties you require (implementable as a generator, uses O(n) working memory).