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.

 Created by Christopher Dunn on Thu, 6 Jul 2006 (PSF)

Required Modules

• (none specified)