Source Code for Module gmisclib.permute

 1  """Find different permutations of an array.""" 
 2   
 3  import Num 
 4   
 5 -def _next_guts(a, n): 
 6          """Increments the array.""" 
 7          o = Num.array(a, copy=True) 
 8          o[0] += 1 
 9          for i in range(len(o)): 
10                  if o[i] >= n: 
11                          o[i] = 0 
12                          if i+1 >= n: 
13                                  return None 
14                          else: 
15                                  o[i+1] += 1 
16          return o 
17   
18 -def _good(p): 
19          """Tests if the array is a valid permutation.""" 
20          used = Num.zeros(p.shape, Num.Int) 
21          for i in p: 
22                  if used[i]: 
23                          return 0 
24                  used[i] = 1 
25          return 1 
26   
27   
28 -def next(a, n): 
29          """Finds the first valid permutation of n items after a. 
30          A valid permutation is an array of length n which 
31          contains values from 0 to n-1, once each. 
32          This function returns the lexicographically next permutation; 
33          it's input need not be a valid permutation, but all the 
34          entries of a should be in the range 0 to n-1, inclusive. 
35          """ 
36          while 1:        # Klugey, slow implementation. 
37                  a = _next_guts(a, n) 
38                  if a is None or _good(a): 
39                          return a 
40          return None 
41   
42 -def factorial(n): 
43          if n == 1: 
44                  return 1 
45          return n * factorial(n-1) 
46   
47 -def permutations(n): 
48          """Returns an array of all the n! permutations of n objects.""" 
49          o = [] 
50          p = Num.zeros((n,), Num.Int) 
51          if _good(p): 
52                  o.append(p)     # Only for n==0 
53          while 1: 
54                  p = next(p, n) 
55                  if p is None: 
56                          assert len(o)==factorial(n) 
57                          return o 
58                  o.append(p) 
59          return None 
60   
61   
62  if __name__ == '__main__': 
63          assert factorial(5) == 120 
64          p1 = permutations(1) 
65          assert len(p1) == 1 
66          assert len(p1[0]) == 1 
67          assert p1[0][0] == 0 
68          p2 = permutations(2) 
69          assert len(p2)==2 
70          assert len(p2[0]) == 2 
71          assert p2[0][0] == 1 
72          assert p2[0][1] == 0 
73          assert p2[1][0] == 0 
74          assert p2[1][1] == 1 
75