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

itertools.permutations does exactly what you want. you might make of use of reversed built-in as well

Answer 2

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)

Answer 3

How about this:

from itertools import permutations

def rev_generator(plist):
    reversed_elements = set()
    for i in permutations(plist):
        if i not in reversed_elements:
            reversed_i = tuple(reversed(i))
            reversed_elements.add(reversed_i)
            yield i

>>> list(rev_generator([1,2,3]))
[(1, 2, 3), (1, 3, 2), (2, 1, 3)]

Also, if the return value must be a list, you could just change the yield i to yield list(i), but for iteration purposes, the tuples will work just fine.

Answer 4

Here is code that does the trick. To get rid of the dups I noticed that for your list if the value of the first location is greater than the value of the last location then it will be a dup. I create a map to keep track of where each item was in the list to start with and then use that map to do the test. The code also does not use recursion so it keeps its memory footprint small. Also the list can be of any type items not just numbers see the last two test cases.

Here is the code.

class Permutation:
    def __init__(self, justalist):
        self._data = justalist[:]
        self._len=len(self._data)
        self._s=[]
        self._nfact=1
        self._map ={}
        i=0
        for elem in self._data:
            self._s.append(elem)
            self._map[str(elem)]=i
            i+=1
            self._nfact*=i
        if i != 0:
            self._nfact2=self._nfact//i

    def __iter__(self):
        for k in range(self._nfact):
            for i in range(self._len):
                self._s[i]=self._data[i]
            s=self._s
            factorial=self._nfact2
            for i in range(self._len-1):
                tempi = (k // factorial) % (self._len - i)
                temp = s[i + tempi]
                for j in range(i + tempi,i,-1):
                    s[j] = s[j-1]
                s[i] = temp
                factorial //= (self._len - (i + 1))

            if self._map[str(s[0])] < self._map[str(s[-1])]:
                yield s




s=[1,2]
print("_"*25)
print("input list:",s)
for sx in Permutation(s):
    print(sx)

s=[1,2,3]
print("_"*25)
print("input list:",s)
for sx in Permutation(s):
    print(sx)

s=[1,2,3,4]
print("_"*25)
print("input list:",s)
for sx in Permutation(s):
    print(sx)

s=[3,2,1]
print("_"*25)
print("input list:",s)
for sx in Permutation(s):
    print(sx)

s=["Apple","Pear","Orange"]
print("_"*25)
print("input list:",s)
for sx in Permutation(s):
    print(sx)

s=[[1,4,5],"Pear",(1,6,9),Permutation([])]
print("_"*25)
print("input list:",s)
for sx in Permutation(s):
    print(sx)

and here is the output for my test cases.

_________________________
input list: [1, 2]
[1, 2]
_________________________
input list: [1, 2, 3]
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
_________________________
input list: [1, 2, 3, 4]
[1, 2, 3, 4]
[1, 2, 4, 3]
[1, 3, 2, 4]
[1, 3, 4, 2]
[1, 4, 2, 3]
[1, 4, 3, 2]
[2, 1, 3, 4]
[2, 1, 4, 3]
[2, 3, 1, 4]
[2, 4, 1, 3]
[3, 1, 2, 4]
[3, 2, 1, 4]
_________________________
input list: [3, 2, 1]
[3, 2, 1]
[3, 1, 2]
[2, 3, 1]
_________________________
input list: ['Apple', 'Pear', 'Orange']
['Apple', 'Pear', 'Orange']
['Apple', 'Orange', 'Pear']
['Pear', 'Apple', 'Orange']
_________________________
input list: [[1, 4, 5], 'Pear', (1, 6, 9), <__main__.Permutation object at 0x0142DEF0>]
[[1, 4, 5], 'Pear', (1, 6, 9), <__main__.Permutation object at 0x0142DEF0>]
[[1, 4, 5], 'Pear', <__main__.Permutation object at 0x0142DEF0>, (1, 6, 9)]
[[1, 4, 5], (1, 6, 9), 'Pear', <__main__.Permutation object at 0x0142DEF0>]
[[1, 4, 5], (1, 6, 9), <__main__.Permutation object at 0x0142DEF0>, 'Pear']
[[1, 4, 5], <__main__.Permutation object at 0x0142DEF0>, 'Pear', (1, 6, 9)]
[[1, 4, 5], <__main__.Permutation object at 0x0142DEF0>, (1, 6, 9), 'Pear']
['Pear', [1, 4, 5], (1, 6, 9), <__main__.Permutation object at 0x0142DEF0>]
['Pear', [1, 4, 5], <__main__.Permutation object at 0x0142DEF0>, (1, 6, 9)]
['Pear', (1, 6, 9), [1, 4, 5], <__main__.Permutation object at 0x0142DEF0>]
['Pear', <__main__.Permutation object at 0x0142DEF0>, [1, 4, 5], (1, 6, 9)]
[(1, 6, 9), [1, 4, 5], 'Pear', <__main__.Permutation object at 0x0142DEF0>]
[(1, 6, 9), 'Pear', [1, 4, 5], <__main__.Permutation object at 0x0142DEF0>]

Answer 5

this is an implementation of onebyone's suggestion

from http://en.wikipedia.org/wiki/Permutation#Lexicographical_order_generation The following algorithm generates the next permutation lexicographically after a given permutation. It changes the given permutation in-place.

1. Find the highest index i such that s[i] < s[i+1]. If no such index exists, the permutation is the last permutation.
2. Find the highest index j > i such that s[j] > s[i]. Such a j must exist, since i+1 is such an index.
3. Swap s[i] with s[j].
4. Reverse all the order of all of the elements after index i

the function:

def perms(items):
    items.sort()
    yield items[:]
    m = [len(items)-2]  # step 1
    while m:
        i = m[-1]
        j = [ j for j in range(i+1,len(items)) if items[j]>items[i] ][-1] # step 2
        items[i], items[j] = items[j], items[i] # step 3
        items[i+1:] = list(reversed(items[i+1:])) # step 4
        if items<list(reversed(items)):
            yield items[:]
        m = [ i for i in range(len(items)-1) if items[i]<items[i+1] ]  # step 1

checking our work:

>>> foo=list(perms([1,3,2,4,5]))
>>> True in [(list(reversed(i)) in foo) for i in foo]
False

Answer 6

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

Answer 7

Some setup code first:

try:
    from itertools import permutations
except ImportError:
    # straight from http://docs.python.org/library/itertools.html#itertools.permutations
    def permutations(iterable, r=None):
        # permutations('ABCD', 2) --> AB AC AD BA BC BD CA CB CD DA DB DC
        # permutations(range(3)) --> 012 021 102 120 201 210
        pool = tuple(iterable)
        n = len(pool)
        r = n if r is None else r
        if r > n:
            return
        indices = range(n)
        cycles = range(n, n-r, -1)
        yield tuple(pool[i] for i in indices[:r])
        while n:
            for i in reversed(range(r)):
                cycles[i] -= 1
                if cycles[i] == 0:
                    indices[i:] = indices[i+1:] + indices[i:i+1]
                    cycles[i] = n - i
                else:
                    j = cycles[i]
                    indices[i], indices[-j] = indices[-j], indices[i]
                    yield tuple(pool[i] for i in indices[:r])
                    break
            else:
                return

def non_reversed_permutations(iterable):
    "Return non-reversed permutations for an iterable with unique items"
    for permutation in permutations(iterable):
        if permutation[0] < permutation[-1]:
            yield permutation

Answer 8

This is a more concise and faster version of ChristopheD's accepted answer, which I liked a lot. Recursion is great. I made it enforce uniquenss of the incoming list by removing duplicates, however maybe it should just raise an exception instead.

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

def permz(plist):
    plist = sorted(set(plist))
    plen = len(plist)
    limit = fac(plen) / 2
    counter = 0
    if plen==1:
        yield plist
    else:
        for perm in permz(plist[1:]):
            for i in xrange(plen):
                if counter == limit:
                     raise StopIteration
                counter += 1
                yield perm[:i] + plist[0:1] + perm[i:]

# ---- testing ----
plists = [
    list('love'),
    range(5),
    [1,4,2,3,9],
    ['a',2,2.1],
    range(8)]               

for plist in plists:
    perms = list(permz(plist))
    print plist, True in [(list(reversed(i)) in foo) for i in perms]

Answer 9

Here is my implementation:

a = [1,2,3,4]

def p(l):
  if len(l) <= 1:
    yield l
  else:
    for i in range(len(l)):
      for q in p([l[j] for j in range(len(l)) if j != i]):
        yield [l[i]] + q

out = (i for i in p(a) if i < i[::-1])

P function is a regular permu function, yields all possibilities. The filter is done when iterates the result. Simply, it has two possible results, the smaller half of the all permus and the bigger half of the permus. In this example, the out contains the smaller half of the list.

Answer 10

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!
p[0] < p[1] or any other pair would also work, so you also have some control over which half of permutations you get.

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!