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

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).

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!

EDIT: changed completely to keep everything as a generator (never the whole list in memory). Should fulfill the requirements (only calculates half of the possible permutations (not the reverse ones). EDIT2: added shorter (and simpler) factorial function from here.

EDIT3:: (see comments) - a version with improvements can be found in bwopah's version.

def fac(x): 
    return (1 if x==0 else x * fac(x-1))

def all_permutations(plist):
    global counter

    if len(plist) <=1:
        yield plist
    else:
        for perm in all_permutations(plist[1:]):
            for i in xrange(len(perm)+1):
                if len(perm[:i] + plist[0:1] + perm[i:]) == lenplist:
                        if counter == limit:
                             raise StopIteration
                        else:
                             counter = counter + 1
                yield perm[:i] + plist[0:1] + perm[i:]

counter = 0
plist = ['a','b','c']
lenplist = len(plist)
limit = fac(lenplist) / 2

all_permutations_gen = all_permutations(plist)
print all_permutations_gen
print list(all_permutations_gen)