集合是数学上的概念，具有无序、唯一性。两个集合相等是指两个集合中的元素分别相等。那么如何判断集合相等？下面给出四种思路，其中最后一种思路的效率是最高的。

思路一：

最直接的蛮力方法。对集合中的元素逐一比较。时间复杂度为O(n^2)。

1
2
3
4
5
6
7
8
9
10
11
12
13
def is_same_set(s1, s2):
    if len(s1) != len(s2):
        return False
    for item1 in s1:
        for item2 in s2:
            if item1 == item2:
                break
            else:
                continue
        else:
            # 没有找到元素
            return False
    return True

for中悬挂的else会在循环没有被break退出时执行，表明元素item1没有在s2中。

思路二：

第二种思路在第一思路下添加排序，然后位置对应的元素一一比较。时间复杂度为O(nlogn)。

1
2
3
4
5
6
7
def is_same_set(s1, s2):
    s1 = sorted(s1)
    s2 = sorted(s2)
    for index in range(len(s1)):
        if s1[index] != s2[index]:
            return False
    return True

思路三：

把集合存储在散列中，判断一个散列是否在集合中使用的时间为O(1)。Python的内置数据结构set采用散列，此处不需要额外的实现。该算法的时间复杂度O(n)。这是最好的算法。不能有时间复杂度的突破，因为扫描集合一遍也有n个元素。

1
2
3
4
5
6
7
def is_same_set(s1, s2):
    if len(s1) != s2:
        return False
    for item in s1:
        if item not in s2:
            return False
    return True

由于集合具有唯一性（没有相同的元素），当长度相等且s1的元素在s2中都存在，就能保证它们是相等的集合。

可以使用反证法证明。

思路四：

这是一种完美的思路：采用指纹和。同时，该算法对数据结构有兼容性，即使输入的不是集合而是列表list或元组tuple也可以处理。

假定集合s1拥有元素{e1, e2, …, en}。那么它的指纹和为：
r1 = hash(e1) + hash(e2) + … + hash(en)。使用求和是因为和具有交换律，适应集合的无序性。

如果两个集合相同，那么它们的指纹和一定相等（不考虑指纹冲突，因为这是极小概率）

1
2
3
4
5
6
7
8
9
def is_same_set(s1, s2):
    r1 = 0
    for item1 in s1:
        r1 += hash(item1)

    r2 = 0
    for item2 in s2:
        r2 += hash(item2)
    return r1 == r2

该实现对输入有兼容性，可以输入list类型、tuple类型、string类型。

当然，上面的实现是有问题的，仅用来做示例。例如：hash函数只能用于不可变类型，如果集合中有可变类型就会出错。在生存环境中应该考虑这样的输入。