目录
第一关：求给定集合的对角线关系(Diagonal Relation)
本人未系统学习过离散数学，完成此实训只是在熟悉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 functoolsclass 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 adef 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 partitiondef 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 Mdef 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 Mdef 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日。
来源地址：https://blog.csdn.net/wander_alice/article/details/129912997
