algorithm - How to generate permutations of a list without "reverse duplicates" in Python using generators

Question

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.

Answer 1

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!