Welcome, guest | Sign In | My Account | Store | Cart

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

Python, 132 lines
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
"""
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)

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

Created by Christopher Dunn on Thu, 6 Jul 2006 (PSF)
Python recipes (4591)
Christopher Dunn's recipes (5)

Required Modules

  • (none specified)

Other Information and Tasks