-
Notifications
You must be signed in to change notification settings - Fork 0
/
lexisort.py
58 lines (45 loc) · 1.15 KB
/
lexisort.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
# O ( n*m (log n) )
# m is length of string element
def lexicographicsort(args):
listToSort, lexP = args
global lexParam, cache
cache = dict()
lexParam = buildMap(lexP)
return _mergesort(listToSort)
def _mergesort(listToSort):
aSize = len(listToSort)
if aSize == 1:
return listToSort
elif aSize > 1:
middle = aSize/2
aList = listToSort[:middle]
bList = listToSort[middle:]
return merge(_mergesort(aList), _mergesort(bList))
def merge(aList,bList):
tmp = list()
while aList and bList:
if (lexisort(aList[0],bList[0])):
tmp.append(aList.pop(0))
else:
tmp.append(bList.pop(0))
if aList:
tmp.extend(aList)
if bList:
tmp.extend(bList)
return tmp
def lexisort(a,b):
return getMap(a, lexParam) < getMap(b, lexParam)
def buildMap(lexParam):
return dict([(a,k) for a,k in zip(lexParam,range(len(lexParam)))] )
def getMap(s, lexParam):
if s in cache:
return cache[s]
else:
cache[s] = ''.join(str(lexParam[a]) for a in s)
return cache[s]
if __name__ == "__main__":
data = [ (["acb", "abc", "bca"], "abc"),
(["acb", "abc", "bca"], "cba"),
(["aaa", "aa", ""], "a") ];
for d in data:
print d, '=>', lexicographicsort(d)