-
Notifications
You must be signed in to change notification settings - Fork 0
/
Permutation.py
134 lines (112 loc) · 3.64 KB
/
Permutation.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
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
133
134
from copy import deepcopy
from AffineMap import *
class Permutation:
def __init__(self, perm):
self.permutation = perm
#return list of adjacent permutations
def getAdjacent(self):
adjacentList = []
for i in range(0, self.dim-1):
for j in range(i+1, self.dim):
nextPerm = list(self.permutation)
temp = nextPerm[i]
nextPerm[i] = nextPerm[j]
nextPerm[j] = temp
adjacentList.append(Permutation(nextPerm))
def dim(self):
return len(self.permutation)
#what goes to position index under the permutation?
#converts order into innate
def sigmaInv(self, index):
return(self.permutation[index])
#where does index go under the permutation
#converts innate into order
def sigma(self,index):
for i in range(0, self.dim()):
if self.permutation[i] == index:
return i
return -1
def inverse(self):
temp = []
for i in range(0, self.dim()):
temp.append(self.sigmaInv(i))
return Permutation(temp)
#construct identity permutation
@staticmethod
def identity(dim):
temp = []
for i in range(0, dim):
temp.append(i)
return Permutation(temp)
#compose symbols (they need to be same length)
@staticmethod
def compose(perm1, perm2):
p1 = perm1.permutation
p2 = perm2.permutation
temp = []
for i in range(0, len(p1)):
temp.append(p1[p2[i]])
return Permutation(temp)
#return transposition of permutation
def transpose(self, transposition):
newPerm = deepcopy(self.permutation)
if transposition == "R":
temp = newPerm[len(newPerm)-1]
for i in range(1, len(newPerm)):
newPerm[len(newPerm) - i] = newPerm[len(newPerm)-i-1]
newPerm[0] = temp
else:
a = transposition[0]
b = transposition[1]
temp = newPerm[a]
newPerm[a] = newPerm[b]
newPerm[b] = temp
return Permutation(newPerm)
#return AffineMap representation of permutation
def mapRepresentation(self):
b = Permutation.makeZeros(self.dim())
A = []
for i in range(0, self.dim()):
nextRow = []
for j in range(0, self.dim()):
if j == self.sigma(i):
nextRow.append(1)
else:
nextRow.append(0)
A.append(nextRow)
return AffineMap(A, b)
def serialize(self):
rep = {}
rep["permutation"] = self.permutation
return rep
@staticmethod
def deserialize(rep):
return Permutation(rep["permutation"])
def isIdentity(self):
for i in range(1, self.dim()):
if self.permutation[i] != self.permutation[i-1] + 1:
return False
return True
#construct swap permuation of given dimension
@staticmethod
def swap(dim, n1, n2):
swapper = Permutation.identity(dim)
temp = swapper.permutation[n1]
swapper.permutation[n1] = swapper.permutation[n2]
swapper.permutation[n2] = temp
return swapper
@staticmethod
def test():
swap1 = Permutation.swap(5,2,3)
swap2 = Permutation.swap(5,4,1)
swap3 = Permutation.compose(swap1, swap2)
print swap1.permutation
print swap2.permutation
print swap3.permutation
@staticmethod
def makeZeros(n):
temp = []
for i in range(0,n):
temp.append(0.0)
return temp
#Permutation.test()