【头歌educoder】离散数学实训参考-第二章-关系-part1-关系基础

目录

        本人未系统学习过离散数学，完成此实训只是在熟悉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日。