代码收藏家 离散数学实训参考-第二章-关系基础 (Part 1)
目录
第一关：求给定集合的对角线关系(Diagonal Relation)
第二关：关系的合成
第三关：关系的幂运算
第四关：关系的并运算
第五关：转换成关系矩阵
第六关：自反关系的判断
第七关：反自反关系的判断
第八关：对称关系的判断
第九关：非对称关系的判断
第十关：反对称关系的判断
第十一关：传递关系的判断
第十二关：计算自反闭包
第十三关：关系的对称闭包
第十四关：关系的传递闭包
第十五关：利用Warshall算法求传递闭包
第十六关：判断等价关系
第十七关：计算等价类
第十八关：从划分生成等价关系
第十九关：判断半序关系
第二十关：判断逆序关系
第二十一关：判断全序关系
第二十二关：关系矩阵的 join 运算
第二十三关：关系矩阵的 meet 运算
第二十四关：关系矩阵的布尔乘积
代码总和实现
本人未系统学习过离散数学，完成此实训只是在熟悉python。
第一关：求给定集合的对角线关系(Diagonal Relation)
任务简述：添加方法diagonalRelation(self)，返回对角线关系对象 总体思路：NEW rel = [(x, x) for x in self.sets] 相关知识：类实例创建、列表表达式 关卡难度：0.4 代码于文末
第二关：关系的合成
任务简述：重载方法__mul__(self)，用于实现关系的合成。 总体思路：NEW rel = [(x,z) for (x,y) in other.rel for (y1,z) in self.rel if y == y1] 相关知识：类实例创建、列表表达式、方法重载 关卡难度：0.5 代码于文末
第三关：关系的幂运算
任务简述：重载方法__pow__(self, power)，实现关系的幂运算。 总体思路：幂次为-1时求反，幂次为0时求对角线，其他递归运算即可 相关知识：重载、递归 关卡难度：0.7 代码于文末
第四关：关系的并运算
任务简述：重载方法__add__(self, other)，实现加法，即关系的并 总体思路：关系求并集 相关知识：集合的并集运算 关卡难度：0.2 代码于文末
第五关：转换成关系矩阵
任务简述：添加方法toMatrix(self)，实现将序偶形式的关系转换成矩阵形式 总体思路：先把集合化为列表并排序，对矩阵一行一行去赋值 相关知识：列表排序、列表的*运算 关卡难度：0.7 代码于文末
第六关：自反关系的判断
任务简述：添加方法isReflexive(self)，实现对自反性的判断 总体思路：对每个元素进行一次判读，一旦出现某元素不自反，返回False 相关知识：对集合的遍历、in、not in 关卡难度：0.4 代码于文末
第七关：反自反关系的判断
任务简述：添加方法isIrreflexive(self)，实现对反自反性的判断 总体思路：对每个元素进行一次判读，一旦出现某元素自反，返回False 相关知识：对集合的遍历、in、not in 关卡难度：0.4 代码于文末
第八关：对称关系的判断
任务简述：添加方法isSymmetric(self)，实现对对称性的判断 总体思路：对每个元素进行一次判读，一旦出现某元素不对称，返回False 相关知识：对集合的遍历、in、not in 关卡难度：0.4 代码于文末
第九关：非对称关系的判断
任务简述：添加方法isAsymmetric(self)，实现对非对称性的判断 总体思路：对每个元素进行一次判读，一旦出现某元素对称，返回False 相关知识：对集合的遍历、in、not in 关卡难度：0.4 代码于文末
第十关：反对称关系的判断
任务简述：添加方法isAntiSymmetric(self)，实现对反对称性的判断 总体思路：一旦出现某元素对称且不位于对角线，返回False 相关知识：对集合的遍历、in、not in 关卡难度：0.5 代码于文末
第十一关：传递关系的判断
任务简述：添加方法isTransitive(self)，实现对传递性的判断 总体思路：对关系遍历，一旦出现某元素传递失败，返回False 相关知识：对集合的遍历、in、not in 关卡难度：0.7 代码于文末
第十二关：计算自反闭包
任务简述：添加方法reflexiveClosure(self)，计算并返回自反闭包 总体思路：与对角线关系求并 相关知识：集合的并运算 关卡难度：0.4 代码于文末
第十三关：关系的对称闭包
任务简述：添加方法symmetricClosure(self)，计算并返回对称闭包 总体思路：求反(-1次幂)的结果与自身之并 相关知识：集合的并运算 关卡难度：0.4 代码于文末
第十四关：关系的传递闭包
任务简述：添加方法transitiveClosure(self)，按幂运算计算并返回传递闭包 总体思路：结果 = 相关知识：集合的并运算 关卡难度：0.6 代码于文末
第十五关：利用Warshall算法求传递闭包
任务简述：添加方法__warshall(self, a)，计算并返回新的关系矩阵，a为关系矩阵 总体思路：遍历关系矩阵，每遇到一个1，对该列重新赋值，赋值关系见代码 相关知识：Warshall-Roy算法、 关卡难度：1.5 代码于文末
第十六关：判断等价关系
任务简述：添加函数isEquivalenceRelation(rel)，判断是否是等价关系 总体思路：等价关系具有自反性、对称性与传递性 相关知识：无 关卡难度：0.2 代码于文末
第十七关：计算等价类
任务简述：添加函数createPartition(rel)，如果关系是等价关系，计算并返回商集 总体思路：等价关系中，每个元素的等价类都会出现在二元关系的第二项 相关知识：frozenset类型作为集合元素 关卡难度：1 代码于文末
第十八关：从划分生成等价关系
任务简述：添加函数createEquivalenceRelation(patition,A)，根据所给集合A上的划分partition创建等价关系 总体思路：每个等价类的元素与元素之间、元素与自身存在关系 相关知识：生成器(集合化) 关卡难度：1.2 代码于文末
第十九关：判断半序关系
任务简述：添加函数isPartialOrder(rel)，判断关系是否半序 总体思路：半序 = 自反 + 反对称 + 传递；或者求反与本身之交集为对角线 相关知识：集合交运算 关卡难度：0.6 代码于文末
第二十关：判断逆序关系
任务简述：添加函数isQuasiOrder(rel)，判断关系是否半序 总体思路：逆序 = 反自反 + 反对称 + 传递 相关知识：无 关卡难度：0.6 代码于文末
第二十一关：判断全序关系
任务简述：添加函数isLinearOrder(rel)，判断关系是否半序 总体思路：全序 = 半序+；关系矩阵表示为上(下)三角 相关知识：生成器集合化 关卡难度：1.1 代码于文末
第二十二关：关系矩阵的 join 运算
任务简述：添加函数join(rel1, rel2)，返回两个关系矩阵的join(或)运算矩阵 总体思路：矩阵或运算 | 相关知识：列表 关卡难度：0.8 代码于文末
第二十三关：关系矩阵的 meet 运算
任务简述：添加函数meet(rel1, rel2)，返回两个关系矩阵的meet(与)运算矩阵 总体思路：矩阵与运算 & 相关知识：列表 关卡难度：0.8 代码于文末
第二十四关：关系矩阵的布尔乘积
任务简述：添加函数booleanProduct(rel1, rel2)，返回两个关系矩阵的布尔乘积 总体思路：线性代数、矩阵乘法、注意顺序 相关知识：列表表达式、if长句、zip打包 关卡难度：1 代码于文末
代码总和实现
import functools
class Relation(object):
def __init__(self, sets, rel):
# rel为sets上的二元关系
assert not(len(sets)==0 and len(rel) > 0) # 不允许sets为空而rel不为空
assert sets.issuperset(set([x[0] for x in rel]) | set([x[1] for x in rel])) # 不允许rel中出现非sets中的元素
self.rel = rel
self.sets = sets
def __str__(self):
relstr = '{}'
setstr = '{}'
if len(self.rel) > 0:
relstr = str(self.rel)
if len(self.sets) > 0:
setstr = str(self.sets)
return 'Relation: ' + relstr + ' on Set: ' + setstr
def __eq__(self, other):
return self.sets == other.sets and self.rel == other.rel
def diagonalRelation(self):
# 返回一个给定集合(self.sets)的对角线关系对象
return Relation(self.sets, set([(a, a) for a in self.sets]))
def __mul__(self, other):
# 返回合成的结果，为一个Relation对象
assert self.sets == other.sets # 必须满足self和other的A->B的映射空间相同
# 注意序偶
return Relation(self.sets, set([(x, y1) for x, y in other.rel for x1, y1 in self.rel if y == x1]))
def __pow__(self, power, modulo=None):
assert power >= -1 # 必须满足幂次>=-1
if power == -1: # 求反
return Relation(self.sets, set([(x, y) for y, x in self.rel]))
elif power == 0: # 求对角线
return self.diagonalRelation()
return self ** (power - 1) * self # 递归：*已经重载
def __add__(self, other):
assert self.sets == other.sets # 必须满足元素相同
return Relation(self.sets, self.rel)
def toMatrix(self):
"""将序偶集合形式的关系转换为矩阵"""
matrix = []
elems = sorted(list(self.sets)) # 为保证矩阵的唯一性，需对self.sets中的元素先排序
line = [0] * len(self.sets)
for elem in elems:
for x, y in self.rel:
if x == elem:
line[elems.index(y)] = 1
matrix.append(line)
line = [0] * len(self.sets)
return matrix
def isReflexive(self):
"""判断是否自反"""
for x in self.sets:
if (x, x) not in self.rel:
return False
return True
def isIrreflexive(self):
"""判断是否 反自反"""
for x in self.sets:
if (x, x) not in self.rel:
return False
return True
def isSymmetric(self):
"""判断是否 对称"""
for x, y in self.rel:
if (y, x) not in self.rel:
return False
return True
def isAsymmetric(self):
"""判断是否 非对称"""
for x, y in self.rel:
if (y, x) in self.rel:
return False
return True
def isAntiAsymmetric(self):
"""判断是否 非对称"""
for x, y in self.rel:
if (y, x) in self.rel and x != y:
return False
return True
def isTransitive(self):
"""判断是否 传递"""
for x, y in self.rel:
for x1, y1 in self.rel:
if x1 == y:
if (x, y1) not in self.rel:
return False
return True
def reflexiveClosure(self):
"""计算自反闭包"""
return self + self.diagonalRelation()
def symmetricClosure(self):
"""对称闭包"""
return self + self ** -1
def transitiveClosure(self):
"""传递闭包"""
closure = self
for i in range(2, len(self.sets) + 1):
if closure.isTransitive(): # 反正是或运算，可以省此判断，或许还会更快算得
break
closure = closure + self ** i
return closure
def transitiveClosure3(self):
# 该方法利用Roy-Warshall计算传递闭包
# 现将关系转换为矩阵，再调用__warshall函数
m = self.toMatrix()
return self.__warshall(m)
def __warshall(self, a): # 参数a为关系矩阵
assert (len(row) == len(a) for row in a)
n = len(a)
# Roy-Warshall求传递闭包的算法
for r in range(n):
for c in range(len(a[r])):
if a[c][r] == 1:
for k in range(n):
a[c][k] = a[c][k] | a[r][k] # .......
return a
def isEquivalenceRelation(rel: Relation):
"""判断等价关系"""
return rel.isReflexive() and rel.isSymmetric() and rel.isTransitive()
def createPartition(rel: Relation):
"""对给定的Relation对象rel，求其决定的rel.sets上的划分"""
# 如果rel不是等价关系，返回空集
if not isEquivalenceRelation(rel):
print("The given relation is not an Equivalence Relation")
return set([])
# 如rel是等价关系，求划分、商集
partition = set([])
for elem in rel.sets: # 给个元素的等价类
partition.add(frozenset(y for x, y in rel.rel if x == elem))
return partition
def createEquivalenceRelation(partition, A):
# 根据所给集合A的划分partition创建等价关系
assert functools.reduce(lambda x, y: x.union(y), partition) == A # 断言保证 ...
# 每个等价类的元素与元素之间、元素与自身存在关系
return Relation(A, set((a,b) for part in partition for a in part for b in part))
def isPartialOrder(rel: Relation):
"""判断是否 半序 = 自反 + 反对称 + 传递"""
return (rel ** (-1)).rel.intersection(rel.rel) == set((x, x) for x in rel.sets)
# return rel.isReflexive() and rel.isAntiSymmetric() and rel.isTransitive()
def isQuasiOrder(rel):
"""判断是否 拟序 = 反自反 + 反对称 + 传递"""
# return (rel ** (-1)).rel.intersection(rel.rel) == set()
return rel.isIrreflexive() and rel.isAntiSymmetric() and rel.isTransitive()
def isLinearOrder(rel: Relation):
"""判断是否 全序 = 半序+ = (自反+) + 反对称 + 传递"""
if not isPartialOrder(rel):
return False
else:
# 由于带有传递性：所以第二个==可以不用
return set(x for x, y in rel.rel if x != y) == rel.sets == set(y for x, y in rel.rel if x != y)
def join(rel1: Relation, rel2: Relation):
"""实现关系矩阵的join运算"""
assert rel1.sets == rel2.sets
# 首先得到二者的矩阵
M1 = rel1.toMatrix()
M2 = rel2.toMatrix()
m = len(M1)
n = m
M = [] # 实现关系矩阵的join运算，结果存于M中
for r in range(m):
row = [0] * n
for c in range(n):
row[c] = M1[r][c] | M2[r][c] # 或
M.append(row)
return M
def meet(rel1: Relation, rel2: Relation):
"""实现关系矩阵的meet运算"""
assert rel1.sets == rel2.sets
# 首先得到二者的矩阵
M1 = rel1.toMatrix()
M2 = rel2.toMatrix()
m = len(M1)
n = m
M = [] # 实现关系矩阵的meet运算，结果存于M中
for r in range(m):
row = [0] * n
for c in range(n):
row[c] = M1[r][c] & M2[r][c] # 与
M.append(row)
return M
def booleanProduct(rel1: Relation, rel2: Relation):
assert rel1.sets == rel2.sets # 保证了矩阵大小一致
# 首先得到二者的矩阵
M1 = rel1.toMatrix()
M2 = rel2.toMatrix()
m = len(M1)
n = m
M = [] # 结果存于M中
for r in range(m):
row_M1_r = M1[r] # 准备M1矩阵的行
row_M_r = [0] * n
for c in range(n):
col_M2_c = [M2[r_2][c] for r_2 in range(m)] # 准备M2矩阵的列
# 计算r行c列的结果
row_M_r[c] = 1 if sum([x & y for x, y in zip(row_r, col_M2_c)]) else 0
M.append(row_M_r)
return M
初笔于2023年4月2日。
