目录
第一关:求给定集合的对角线关系(Diagonal Relation)
第二关:关系的合成
第三关:关系的幂运算
第四关:关系的并运算
第五关:转换成关系矩阵
第六关:自反关系的判断
第七关:反自反关系的判断
第八关:对称关系的判断
第九关:非对称关系的判断
第十关:反对称关系的判断
第十一关:传递关系的判断
第十二关:计算自反闭包
第十三关:关系的对称闭包
第十四关:关系的传递闭包
第十五关:利用Warshall算法求传递闭包
第十六关:判断等价关系
第十七关:计算等价类
第十八关:从划分生成等价关系
第十九关:判断半序关系
第二十关:判断逆序关系
第二十一关:判断全序关系
第二十二关:关系矩阵的 join 运算
第二十三关:关系矩阵的 meet 运算
第二十四关:关系矩阵的布尔乘积
代码总和实现
本人未系统学习过离散数学,完成此实训只是在熟悉python。文章来源:https://www.toymoban.com/news/detail-724746.html
第一关:求给定集合的对角线关系(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日。文章来源地址https://www.toymoban.com/news/detail-724746.html
到了这里,关于【头歌educoder】离散数学实训参考-第二章-关系-part1-关系基础的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!