/
perm.py
79 lines (57 loc) · 2.02 KB
/
perm.py
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
import sys
def perm_1(l, c = 0):
if len(l) > 1:
for c_pass in xrange(0, len(l)):
print "Removing %s from %s, and" % (l[c_pass], l),
print "Passing %s with c_pass=%d" % (l[0:c] + l[c+1:],
c_pass)
perm(l[0:c]+l[c+1:], c_pass)
else:
try:
print "1st:", l[c]
except:
print sys.exc_info()
try:
print "Rest:", l[0:c]+l[c+1:]
print "List:", l
except:
print sys.exc_info()
# abc: a, bc -> ab, c -> abc
# -> ac, b -> acb
# b, ac -> ba, c -> bac
# -> bc, a -> bca
# c, ab -> ca, b -> cab
# -> cb, a -> cba
def perm_2(l, lorg = None):
for c in xrange(0, len(l)):
elem = l[c]
rest = l[0:c] + l[c+1:]
print "Elem is %s, rest is %s" % (elem, rest)
perm(rest)
# abc: a, bc -> ab, c -> abc
# -> ac, b -> acb
# b, ac -> ba, c -> bac
# -> bc, a -> bca
# c, ab -> ca, b -> cab
# -> cb, a -> cba
def perm(l, lorg = [], recur_level = 0, permutations = []):
if len(l) == 0:
#print "Zero!, lorg = %s " % (lorg)
permutations.append(lorg)
for c in xrange(0, len(l)):
elem = l[c]
rest = l[0:c] + l[c+1:]
#lorg.append(elem)
#print "Elem is %s, rest is %s, lorg is %s, level is %s" % (elem, rest, lorg + [elem], recur_level)
perm(rest, lorg + [elem], recur_level + 1, permutations)
#print "Returning from level %s... " % (recur_level)
return permutations
def main(l):
#for c in perm(l):
# print "Permutation = %s" % (c)
permutations = perm(l)
print "The permutations are %s" % (permutations)
print "The number of permutations of %d elements is %d." % (len(l), len(permutations))
l = [1, 2, 3, 4, 5, 6, 7, 8]
if __name__ == "__main__":
main(l)