【Educoder离散数学实训】集合及其基本运算的实现

别催了别催了，我现在是真整不明白Python的语法逻辑了。可能以后博客就以记录和复盘为主了吧，讲解可能水平不够了啊哈哈哈哈

T1 set简单应用

第一题是介绍了$set$。$set$可以用$for$直接访问，但是不能直接索引。
$set$的内部逻辑是红黑树，时间复杂度是$O(nlogn)$。本质上讲$set$的内部是有序的，只是$Python$或许为了优化复杂度砍掉了$set$的索引功能，与传统数据结构类似。

def readAndPrintUniqueWords(filename):
    infile = open(filename, 'r')
    #**********  Begin  **********#
    #请在此区间内编程完成函数代码
    txt = infile.readlines()
    s = set()
    for mdl in txt :
        pre = len(s)
        s.add(mdl)
        aft = len(s)
        if aft > pre :
            print(mdl, end = '')
    #请在此区间内编程完成函数代码
    #**********  End  **********#
    infile.close()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

T2 《仲夏夜之梦》中的回文单词对

我的噩梦开始了。
这题就垃圾的不行，题面啥也不说全靠猜。
思路是容易的，两个$set$，一个存答案一个存所有的单词，每次对于一个新单词只需要看一下他的$reverse$是不是在全集里，如果在的话就把他和他的$reverse$同时放到答案里。

def shakeSpeare(filename):
    #**********  Begin  **********#
    #请在此区间内编程实现函数功能
    # [::-1]
    infile = open(filename, 'r')
    txt = infile.read()
    txt = txt.replace('\n', '')
    txt = txt.split()
    reverse, All = set(), set()
    for s in txt :
        if len(s) >= 5 and (s == s[::-1] or (s[::-1] in All)) :
            reverse.add(s), reverse.add(s[::-1])
        All.add(s)
    return reverse
1
2
3
4
5
6
7
8
9
10
11
12
13
14

T3 求幂集

这个题或许有更好的办法？
我选择的是直接状态压缩，从$0$到$2^l-1$，每个数字对应一个包含前导$0$的$l$位二进制数，每个二进制数唯一对应着一种子集的选取情况，枚举之后位运算处理即可。

def powSet(S):
    #**********  Begin  **********#
    #请在此区域内编程
    l = len(S)
    L = list(S)
    ret = set()
    for i in range(2 ** l) :
        mdl = set()
        for j in range(l) :
            if 2 ** j & i :
                mdl.add(L[j])
        ret.add(frozenset(mdl))
    return ret
    #请在此区域内编程
    #**********  End  **********#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

T4 计算n个集合的笛卡尔乘积

看的别的同学给我的答案，我写的那玩意儿元素只能是数不能是$frozenset()$。
说两个思路吧：
第一个就稍微聊一下这个答案吧，估计你们就是来看我叭叭的。
这个递归是容易想的，也是容易写的，但是答案里的有一些操作很有趣。
先贴代码：

def DescartesProduct(*args):
    l = len(args)
    if l == 1 :
        ans, m = set(), len(args[0])
        L = list(args[0])
        for i in range(m) :
            ans.add(tuple(L[i]))
        return ans
    elif l == 2 :
        ans = set()
        for x in args[0] :
            for y in args[1] :
                # if type(y) == tuple :
                #     mdl = list(y)
                #     mdl.append(x)
                #     ans.add(tuple(mdl))
                if type(x) == tuple :
                    mdl = list(x)
                    mdl.append(y)
                    ans.add(tuple(mdl))
                else :
                    ans.add((x, y))
        return ans
    else :
        pre = args[0]
        for x in args[1 :] :
            tmp = DescartesProduct(pre, x)
            pre = tmp
        return pre
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

首先，递归得退出条件是两个，分别是只有一个集合和只有两个集合。
只有一个集合当然是容易的，两个集合的话我们需要进行合并。这里答案的处理很巧妙，他通过判断$x$是否为元组来决定当前的题目情况是两个集合合并还是多个集合合并。
至于为什么是判断$x$而不是判断$y$，因为在多个集合的情况时，我们不断地把返回的答案$pre$放到了递归函数的第一维，也就是说如果出现了元组也只会是第一维出现。
有趣的操作在于，我们可以直接往$\ast args$里面存好几个
第二个思路是全局处理：
假设当前有一个嵌套列表，里面存好了前$i$个集合的笛卡尔乘积，分别放在了列表的前$m$位，每个位置的列表有$i$个元素。对于当前的第$i+1$个集合，我们发现对于它的任何一个元素，都会产生新的$m$个笛卡尔乘积出来。那我们可以提前把列表空间开出来，将新的笛卡尔成绩放在指定位置即可。