Skip to content

Commit 166cd27

Browse files
heqin-zhuheqin-zhu
committed
String matching algorithm, permutation algorithm
1 parent 3b8fa17 commit 166cd27

19 files changed

Lines changed: 479 additions & 36 deletions

‎dataStructure/intervalTree.py‎

Lines changed: 11 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -84,7 +84,7 @@ def genNum(n =10,upper=10):
8484
return nums.values()
8585

8686
def buildTree(n=10,nums=None,visitor=None):
87-
if nums is None or nums ==[]: nums = genNum(n)
87+
#if nums is None or nums ==[]: nums = genNum(n)
8888
tree = intervalTree()
8989
print(f'build a red-black tree using {nums}')
9090
for i in nums:
@@ -100,6 +100,7 @@ def visitor(t,val):
100100
print('-'*5+ 'in-order visit' + '-'*5)
101101
for i,j in enumerate(tree.sort()):
102102
print(f'{i+1}: {j}')
103+
return tree
103104

104105
def testSuc(nums=None):
105106
tree,nums = buildTree(nums=nums)
@@ -113,10 +114,16 @@ def testDelete(nums=None):
113114
print(f'deleting {i}')
114115
tree.delete(i[0])
115116
print(tree)
117+
return tree
116118

117119
if __name__=='__main__':
118120
lst = [(0,3),(5,8),(6,10),(26,26),(25,30),(8,9),(19,20),(15,23),(16,21),(17,19)]
119-
lst = None
121+
#lst = None
120122
#testSuc(lst)
121-
#testInsert(lst)
122-
testDelete(lst)
123+
tree = testInsert(lst)
124+
#tree,_= buildTree(lst)
125+
while 1:
126+
a =int( input('low:'))
127+
b =int( input('high:'))
128+
res = tree.search(a,b)
129+
print(res)

‎dataStructure/redBlackTree.py‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -286,6 +286,7 @@ def buildTree(n=10,nums=None,visitor=None):
286286
print(f'build a red-black tree using {nums}')
287287
for i in nums:
288288
rbtree.insert(node(i))
289+
print(rbtree)
289290
if visitor:
290291
visitor(rbtree,i)
291292
return rbtree,nums

‎divideAndConquer/min_distance_of_n_points.py‎

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -107,18 +107,18 @@ def test(f=minDistance_n2):
107107
print('result: {:.2f} {} {}\n'.format(minD, p,q))
108108

109109
def genData(n,unique=True):
110+
upper = 1000000
110111
if unique:
111112
points = set()
112113
for i in range(n):
113-
points.add(point(randint(1,1000),randint(1,1000)))
114+
points.add(point(randint(1,upper),randint(1,upper)))
114115
return list(points)
115-
else:return [point(randint(1,1000),randint(1,1000)) for i in range(n)]
116+
else:return [point(randint(1,upper),randint(1,upper)) for i in range(n)]
116117

117118
if __name__ =='__main__':
118-
n = 10000
119+
n = 1000
119120
points = genData(n, unique=True)
120121
print('min distance of {} points'.format(n))
121122
#print(sorted(points))
122123
test(minDistance_n2)
123124
test(minDistance_nlogn)
124-

‎dynamicProgramming/lcs.hs‎

Lines changed: 0 additions & 8 deletions
This file was deleted.

‎dynamicProgramming/lcs.py‎

Lines changed: 14 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -29,17 +29,22 @@ def lcs2(a,b):
2929
m,n= len(a),len(b)
3030
board = [[] for i in range(n+1)]
3131
for i in range(m):
32-
last = []
32+
upperLevel = board[0].copy()
3333
for j in range(n):
34+
tmp = board[j+1].copy()
3435
if a[i]==b[j]:
35-
board[j+1] =board[j]+[a[i]]
36-
elif len(board[j+1]) < len(last):
37-
board[j+1] = last
38-
last = board[j+1]
36+
board[j+1] = upperLevel+[a[i]]
37+
elif len(board[j+1]) < len(board[j]):
38+
board[j+1] = board[j].copy() # copy is needed
39+
upperLevel = tmp
3940
return board[n]
4041

4142
if __name__ =='__main__':
42-
a="dsaffqewqfqewregqwefqwe"
43-
b="adsfsfs3qt5yhyh24efwq"
44-
print(lcs(a,b))
45-
print(lcs2(a,b))
43+
a = 'ABCBDAB'
44+
b = 'BDCABA'
45+
print('s1:',a)
46+
print('s2:',b)
47+
while 1:
48+
print('lcs:',lcs2(a,b))
49+
a = input('s1: ')
50+
b = input('s2: ')

‎math/permute_back_track.py‎

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,12 @@
1+
def permute(n):
2+
def _util(lst,i):
3+
if i==n:print(lst)
4+
else:
5+
for j in range(i,n):
6+
lst[i],lst[j]=lst[j],lst[i]
7+
_util(lst,i+1)
8+
lst[i],lst[j]=lst[j],lst[i]
9+
_util([i for i in range(n)],0)
10+
11+
if __name__=='__main__':
12+
permute(5)

math/cantor.c renamed to math/permute_cantor.c

Lines changed: 19 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -11,7 +11,7 @@ void calFac(int n)
1111
}
1212
}
1313

14-
void getArrangement(int *arr,int n,int sum)
14+
void permute(int *arr,int n,int sum)
1515
{
1616
/*sum表示全排列由小到大排序后的名次,从0 开始计数, 由名次求出 n位的排列存储到 arr 中*/
1717
int i,j,ct=0,k, ct2;
@@ -36,3 +36,21 @@ void getArrangement(int *arr,int n,int sum)
3636
}
3737
}
3838

39+
void printArr(int *p,int n)
40+
{
41+
for(int i=0;i<n;++i)printf("%d, ",p[i]);
42+
printf("\n");
43+
}
44+
45+
int main()
46+
{
47+
int n = 5,arr[n];
48+
calFac(n);
49+
for(int i=0;i<5;++i)arr[i]=i;
50+
for(int i=0;i<fac[n];++i){
51+
printArr(arr,n);
52+
permute(arr,n,i);
53+
}
54+
return 0;
55+
}
56+

‎math/permute_divide_and_conquer.py‎

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,12 @@
1+
def permute(lst,n):
2+
''' O(n!), optimal'''
3+
if n==1:print(lst)
4+
else:
5+
for i in range(n):
6+
lst[i],lst[n-1] = lst[n-1],lst[i]
7+
permute(lst,n-1)
8+
lst[i],lst[n-1] = lst[n-1],lst[i]
9+
10+
if __name__=='__main__':
11+
n = 3
12+
permute([i for i in range(n)],n)

math/arrangement.c renamed to math/permute_next_arrangement.c

File renamed without changes.

‎math/primesLEn.hs‎

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,3 @@
1+
genPrimes 2= [2]
2+
genPrimes n = let li = genPrimes $n-1
3+
in if all (\x-> mod n x /=0) li then n:li else li

0 commit comments

Comments
 (0)