[frames] | no frames]

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

 Generated by Epydoc 3.0.1 on Thu Sep 22 04:25:16 2011 http://epydoc.sourceforge.net