Title: Computing permutations with duplicates
Submitter: Christopher Dunn (other recipes)
Last Updated: 2006/07/07
Version no: 1.2
Category: Algorithms

Description:

This handles duplicate values in the list. It could easily be made a generator, and it does not require recursion.

Source: Text Source

"""
Compute permutations.
"""

def permute_next(values):
    """
    Alter the list of values in-place to produce to the next permutation
    in lexicographical order.
    
    'values' must support slicing and ::reverse().
    """
    last = len(values) - 1
    a = last
    while a > 0:
        b = a
        a -= 1
        if values[a] < values[b]:
            c = last
            while values[a] >= values[c]: # >= allows duplicates
                c -= 1
            values[a], values[c] = values[c], values[a] # Swap.
            values[b:] = values[:b-1:-1] # Reverse.
            return
    values.reverse()

def permute_prev(values):
    """
    Alter the list of values in-place to produce to the previous permutation
    in lexicographical order.
    
    'values' must support slicing and ::reverse().
    """
    last = len(values) - 1
    a = last
    while a > 0:
        b = a
        a -= 1
        if values[a] > values[b]:
            c = last
            while values[a] <= values[c]: # <= allows duplicates
                c -= 1
            values[a], values[c] = values[c], values[a] # Swap.
            values[b:] = values[:b-1:-1] # Reverse.
            return
    values.reverse()

import unittest
class PermutationTests(unittest.TestCase):
    def count(self, orig, expect):
        values = orig[:]
        seen = []
        while values not in seen:
            seen.append(values[:])
            permute_next(values)
        self.failUnless(list(reversed(orig)) in seen)
        self.failUnless(list(sorted(orig)) in seen)
        self.failUnless(list(reversed(sorted(orig))) in seen)
        values.sort()
        start = seen.index(values)
        for _ in range(len(orig)+1):
            current = values[:]
            permute_next(values)
            self.failUnless( current < values or values == seen[start] )
        for _ in range(len(orig)+1):
            current = values[:]
            permute_prev(values)
            self.failUnless( current > values or current == seen[start] )
        self.assertEqual(expect, len(seen))
     def test0(self):
        self.count( [], 1 )
    def test1(self):
        self.count( [42], 1 )
    def test2(self):
        self.count( [1,1], 1 )
        self.count( [1,2], 2 )
        self.count( [2,1], 2 )
    def test3(self):
        self.count( range(3), 6 )
        self.count( range(3,0,-1), 6 )
        self.count( [1,1,1], 1 )
        self.count( [1,1,2], 3 )
        self.count( [1,2,1], 3 )
        self.count( [2,1,1], 3 )
        self.count( [1,2,2], 3 )
        self.count( [2,1,2], 3 )
        self.count( [2,2,1], 3 )
    def test4(self):
        self.count( range(4), 24 )
        self.count( range(4,0,-1), 24 )
        self.count( [1,1,1,1], 1 )
        self.count( [1,1,1,2], 4 )
        self.count( [1,1,2,1], 4 )
        self.count( [1,2,1,1], 4 )
        self.count( [2,1,1,1], 4 )
        self.count( [1,2,2,2], 4 )
        self.count( [2,1,2,2], 4 )
        self.count( [2,2,1,2], 4 )
        self.count( [2,2,2,1], 4 )
        self.count( [1,1,2,2], 6 )
        self.count( [1,2,2,1], 6 )
        self.count( [2,2,1,1], 6 )
        self.count( [2,1,1,2], 6 )
        self.count( [1,2,1,2], 6 )
        self.count( [2,1,2,1], 6 )
    def test5(self):
        self.count( ['c', 'a', 'a', 'a', 'c', 'd', 'd'], 210 )

def _test():
    unittest.main()

def run(values):
    seen = []
    while values not in seen:
        print values
        seen.append(values[:])
        permute_prev(values)


if __name__ == '__main__':
    from optparse import OptionParser
    parser = OptionParser(usage='%prog [options] x y z ...',
                            description='Show all permutations.')
    parser.add_option('-t', '--test', action='store_true', help='Run tests.')
    opts, extras = parser.parse_args()
    if opts.test:
        import sys
        sys.argv[1:] = extras
        _test()
    try:
        run(map(int, extras))
    except ValueError:
        run(extras)

Discussion:

Most permutation algorithms (e.g. www.cs.rpi.edu/~musser/gp/algorithm-concepts/perm-screen.pdf) assume unique elements, but that is not very practical.

You might prefer a function which returns a new list, and then perhaps a generator would be in order. However, permuting lists in-place allows them to be arbitrarily large. The lack of recursion also facilitates large lists.

See also
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/496819