1 """ Calculate and return a list of all permutations of
2 a list of items given as parameters.
3
4 permute0 is the most complete implementation,
5 permute2/3 are ownly shown to look at how this
6 influences performance.
7 """
8
9 def permute0(alist):
10 """ generic implementation """
11 l = len(alist)
12 if l==2:
13 a,b = alist
14 return ([a,b], [b,a])
15 elif l>2:
16 res = []
17 first, rest = alist[:1], alist[1:]
18 for perm in permute0(rest):
19 res.append(first+perm)
20 res.append(perm+first)
21 return res
22 elif l==1:
23 return (alist,)
24 else:
25 return []
26
27 def permute2(alist):
28 """ permute2 is a bit faster than permute0,
29 but only valid for len(alist)>=2
30 """
31 if len(alist)==2:
32 a,b = alist
33 return ([a,b], [b,a])
34 else:
35 res = []
36 first, rest = alist[:1], alist[1:]
37 for perm in permute2(rest):
38 res.append(first+perm)
39 res.append(perm+first)
40 return res
41
42 def permute3(alist):
43 """ permute3 is a bit faster than permute0,
44 but only valid for len(alist)>=3
45 """
46 if len(alist)==3:
47 a,b,c = alist
48 return ([a,b,c], [b,a,c], [c,a,b], [c,b,a])
49 else:
50 res = []
51 first, rest = alist[:1], alist[1:]
52 for perm in permute3(rest):
53 res.append(first+perm)
54 res.append(perm+first)
55 return res
56
57 def timer(fun,r):
58 from time import clock
59 data = range(0,r)
60 t0 = clock()
61 p = fun(data)
62 t1 = clock()
63 print "t=", t1-t0, "len(p)=", len(p)
64
65
66 timer(permute0, 17)
67 timer(permute2, 17)
68 timer(permute3, 17)
