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

这篇具有很好参考价值的文章主要介绍了【头歌educoder】离散数学实训参考-第二章-关系-part1-关系基础。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

 第一关:求给定集合的对角线关系(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
  • 相关知识:对集合的遍历、innot in
  • 关卡难度:0.4  代码于文末

 第七关:反自反关系的判断

  • 任务简述:添加方法isIrreflexive(self),实现对反自反性的判断
  • 总体思路:对每个元素进行一次判读,一旦出现某元素自反,返回False
  • 相关知识:对集合的遍历、innot in
  • 关卡难度:0.4   代码于文末

 第八关:对称关系的判断

  • 任务简述:添加方法isSymmetric(self),实现对对称性的判断
  • 总体思路:对每个元素进行一次判读,一旦出现某元素不对称,返回False
  • 相关知识:对集合的遍历、innot in
  • 关卡难度:0.4   代码于文末

 第九关:非对称关系的判断

  • 任务简述:添加方法isAsymmetric(self),实现对非对称性的判断
  • 总体思路:对每个元素进行一次判读,一旦出现某元素对称,返回False
  • 相关知识:对集合的遍历、innot in
  • 关卡难度:0.4   代码于文末

 第十关:反对称关系的判断

  • 任务简述:添加方法isAntiSymmetric(self),实现对反对称性的判断
  • 总体思路:一旦出现某元素对称且不位于对角线,返回False
  • 相关知识:对集合的遍历、innot in
  • 关卡难度:0.5   代码于文末

 第十一关:传递关系的判断

  • 任务简述:添加方法isTransitive(self),实现对传递性的判断
  • 总体思路:对关系遍历,一旦出现某元素传递失败,返回False
  • 相关知识:对集合的遍历、innot in
  • 关卡难度:0.7   代码于文末

 第十二关:计算自反闭包

  • 任务简述:添加方法reflexiveClosure(self),计算并返回自反闭包
  • 总体思路:与对角线关系求并
  • 相关知识:集合的并运算
  • 关卡难度:0.4  代码于文末

 第十三关:关系的对称闭包

  • 任务简述:添加方法symmetricClosure(self),计算并返回对称闭包
  • 总体思路:求反(-1次幂)的结果与自身之并
  • 相关知识:集合的并运算
  • 关卡难度:0.4   代码于文末

 第十四关:关系的传递闭包

  •  任务简述:添加方法transitiveClosure(self),按幂运算计算并返回传递闭包
  • 总体思路:结果 = 【头歌educoder】离散数学实训参考-第二章-关系-part1-关系基础,python,笔记
  • 相关知识:集合的并运算
  • 关卡难度: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模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 头歌实训-离散数学-图论!

    5阶无向完全图的边数为:10 设图 G 有 n 个结点, m 条边,且 G 中每个结点的度数不是 k ,就是 k+1 ,则 G 中度数为 k 的节点数是: n(k+1)-2m 若一个图有5个顶点,8条边,则该图所有顶点的度数和为多少?16 他让输出关联矩阵和邻接矩阵这不简单么? 我是直接摆烂了 输出个球呀

    2024年02月04日
    浏览(75)
  • 离散数学(2) 第二章 道路与回路

    (本文为作者期末复习时所写,内容源自教材《图论与代数结构》戴一奇等著,结合了作者本人的一些理解,如有错误,请指出!) 2.1道路与回路 1.【定义】(有向图)简单有向道路 简单有向回路:边不重复出现 初级有向道路 初级有向回路:点不重复出现 2.【定义】(无向

    2024年02月05日
    浏览(33)
  • ​​​​​​​头歌(EduCoder)Java实训作业答案

    搜集整理了一份最新最全的头歌(EduCoder)Java实训作业答案,分享给大家~ (EduCoder)是信息技术类实践教学平台。(EduCoder)涵盖了计算机、大数据、云计算、人工智能、软件工程、物联网等专业课程。超60000个实训案例,建立学、练、评、测一体化实验环境。   第一关 第二关 C

    2024年02月08日
    浏览(44)
  • CSS--头歌(educoder)实训作业题目及答案

    目录 CSS——基础知识 第1关: 初识CSS:丰富多彩的网页样式 第2关: CSS样式引入方式 CSS——基础选择器 第1关: CSS 元素选择器 第2关: CSS 类选择器 第3关: CSS id选择器 CSS——文本与字体样式 第1关: 字体颜色、类型与大小 第2关: 字体粗细与风格 第3关: 文本装饰与文本布局 CSS——

    2024年04月15日
    浏览(138)
  • JavaScript上部分--头歌(educoder)实训作业题目及答案

      目录 JS简介 第1关: JavaScript基础入门 第2关: JavaScript 与 HTML 第3关: JavaScript 变量 JS 数据类型 第1关: JavaScript 数据类型介绍 第2关: JavaScript 数据类型转换 JS运算符 第1关: 算术运算符 第2关: 比较和逻辑运算符 第3关: 条件和赋值运算符 第4关: 运算符的优先级和结合性 JS对象 第

    2024年02月08日
    浏览(34)
  • JavaScript下部分--头歌(educoder)实训作业题目及答案

    目录  JSON 第1关: JSON对象 第2关: JSON数组 第3关: JSON字符串 Math、日期和异常处理 第1关: Math类 第2关: Date类 第3关: JavaScript错误 HTML DOM——文档元素的操作(一) 第1关: 通过id获取文档元素 第2关: 通过类名获取文档元素 第3关: 通过标签名获取文档元素 第4关: html5中获取元素的

    2023年04月26日
    浏览(42)
  • Educoder/头歌JAVA实训——JAVA循环与分支语句编程练习

    为了完成本关任务,你需要掌握:1、数组的定义; 2、循环语句的熟练使用。 实现思路: 可以通过三层循环的方式,第一层循环用于控制百位数的变化,第二层循环用于控制十位数的变化,第三层循环用于控制个位数的变化。 由于题目要求百位数、十位数、个位数互不重复

    2023年04月08日
    浏览(76)
  • JavaScript上部分--头歌(educoder)实训作业题目及答案 JS简介

      目录 JS简介 第1关: JavaScript基础入门 第2关: JavaScript 与 HTML 第3关: JavaScript 变量 JS 数据类型 第1关: JavaScript 数据类型介绍 第2关: JavaScript 数据类型转换 JS运算符 第1关: 算术运算符 第2关: 比较和逻辑运算符 第3关: 条件和赋值运算符 第4关: 运算符的优先级和结合性 JS对象 第

    2023年04月22日
    浏览(166)
  • 头歌(educoder)实训作业题目及答案分享 ——1-4 Java入门 - 分支结构

    📜个人简介 :  作者简介:大家好,我是Passenger.n✌️  支持一下:点赞👍+收藏🌟+留言📪 📣 系列专栏:java基础🍁 ✉️格言:花有重开日,人无再少年!🌞 万事开头难,既然迈开了这一步,那就坚持走下去! 这是我的第一篇博客,希望萌新看了有收获,大佬看了给指

    2024年02月06日
    浏览(105)
  • 头歌Educoder实验:程序设计二(面向对象)_实训3_类外定义成员函数

    第1关:类外定义存取函数 任务描述 本关仍然有一个 Int 类,该类包含一个 int 类型的成员。为其编写存取函数。注意,存取函数要在类外实现。 相关知识 类的定义中,既可以书写成员函数的声明,也可以书写成员函数的定义(即实现)。如果在类中定义成员函数,则该成员

    2024年02月06日
    浏览(58)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包