斯坦福算法专项课程Course1 week4算法实现

这次回顾第四周的算法。

课程地址:https://www.coursera.org/specializations/algorithms

Randomized Selection

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
import numpy as np

def Exchange(A, i, j):
#交换元素的值
p = A[i]
A[i] = A[j]
A[j] = p

def Partion(A, l, r):
#随机选择
index = np.random.randint(l, r + 1)
Exchange(A, index, l)
#选择主元
p = A[l]
i = l + 1
for j in range(l + 1, r + 1):
if (A[j] < p):
Exchange(A, i, j)
i += 1
Exchange(A, l, i - 1)

return i - 1

def Randomized_Selection(A, i):
n = len(A)
if (n == 1):
return A[0]
#返回位置
j = Partion(A, 0, n - 1)
#次序统计量
k = j + 1
p = A[j]
if (i == k):
return p
elif (k > i):
return Randomized_Selection(A[: j], i)
else:
return Randomized_Selection(A[j + 1:], i - k)

#测试
N = int(1e5)
#次序统计量
k = np.random.randint(1, N + 1)
data = np.random.rand(N)
data_sort = np.sort(data)

#测试结果
r1 = Randomized_Selection(data, k)
r2 = data_sort[k - 1]
print(r1 == r2)

Deterministic Selection

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
import numpy as np

def Exchange(A, i, j):
#交换元素的值
p = A[i]
A[i] = A[j]
A[j] = p

def Partion(A, l, r, p):
#找到p的位置
for i in range(l, r + 1):
if (A[i] == p):
index = i
break
#交换位置
Exchange(A, index, l)
i = l + 1
for j in range(l + 1, r + 1):
if (A[j] < p):
Exchange(A, i, j)
i += 1
Exchange(A, l, i - 1)

return i - 1

def Deterministic_Selection(A, i):
n = len(A)
if (n == 1):
return A[0]
C = []
for s in range(0, n, 5):
t = min(n, s + 5)
A[s: t].sort()
#找到中间元素
index = min(s + 2, n - 1)
C.append(A[index])
p = Deterministic_Selection(C, len(C) // 2)
#返回位置
j = Partion(A, 0, n - 1, p)
#次序统计量
k = j + 1
if (i == k):
return p
elif (k > i):
return Deterministic_Selection(A[: j], i)
else:
return Deterministic_Selection(A[j + 1:], i - k)

return A

#测试
N = int(1e5)
#次序统计量
k = np.random.randint(1, N + 1)
data = np.random.rand(N)
data_sort = np.sort(data)
#测试结果
r1 = Deterministic_Selection(data, k)
r2 = data_sort[k - 1]
print(r1 == r2)

Random Contraction Algorithm

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
import numpy as np
import copy

V = {}
with open("../kargerMinCut.txt") as f:
for i in f.readlines():
data = list(map(int, i.strip().split('\t')))
#邻接表
V[data[0]] = np.array(data[1:])

def Random_Contraction_Algorithm(Vertex):
while len(Vertex) > 2:
#选择节点
u = np.random.choice(list(Vertex.keys()))
v = np.random.choice(Vertex[u])
#更新u, v
adj_u = Vertex[u]
adj_v = Vertex[v]
#合并相邻节点
adj_u = np.append(adj_u[adj_u != v], adj_v[adj_v != u])
#更新
Vertex[u] = adj_u
#删除v
Vertex.pop(v)
#更新其余元素
for i in adj_v:
if i != u:
#得到和i相邻的节点
vec = Vertex[i]
#将v替换为u
vec[vec == v] = u
Vertex[i] = vec

n = []
for i in Vertex:
n.append(len(Vertex[i]))
return np.min(n)

n = len(V)
#N = int(n ** 2 * np.log(n))
N = 100
Res = []
for i in range(N):
#深复制
Vertex = copy.deepcopy(V)
#计算结果
num = Random_Contraction_Algorithm(Vertex)
Res.append(num)

print(np.min(Res))