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

这次回顾第四周的算法。

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

Randomized Selection

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

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

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))