如何在不修改原集合的情况下生成含新元素的集合？（递归排列场景）

我发现列表支持+运算，但集合不支持：

[1, 2, 3] + [4]  # Works

{1, 2, 3} + {4}  # Error

使用set.add()方法会修改原集合，且返回None类型，我希望不修改原集合，仅得到添加元素后的新集合。

背景场景 #

我正在编写打印字符串排列的函数，但原函数无法处理含重复字符的字符串：

def my_func1(s, temp, i, n):
    if i == n:
        print(temp)
    
    for x in range(n):
        if s[x] not in temp:
            my_func1(s, temp + s[x], i+1, n)
    
string = 'abcd'
my_func1(string, '', 0, len(string))

为了支持含重复字符的字符串，我尝试用存储元素索引的集合来区分重复字符，但集合不支持+运算导致报错：

def my_func2(s, temp, i, n, hash_set):
    if i == n:
        print(temp)
        return
    
    for x in range(n):
        if x not in hash_set:
            # 报错：集合不支持+运算
            my_func2(s, temp + s[x], i+1, n, hash_set + x)

string = 'abcd'
my_func2(string, '', 0, len(string), {})

不能用hash_set.add(x)后传递参数，因为会修改递归栈中其他函数调用的集合状态。我已经用列表实现了可行代码，但出于性能考虑想改用集合：

def my_func3(s, temp, i, n, hash_list): # 支持重复字符但用列表作为哈希
    if i == n:
        print(temp)
        return
    
    for x in range(n):
        if x not in hash_list:
            my_func3(s, temp + s[x], i+1, n, hash_list + [x])

string = 'abcd'
my_func3(string, '', 0, len(string), [])

解决方案 #

想要不修改原集合生成新集合，有两种高效方法：

• 方法1：集合解包语法
  通过{*原集合, 新元素}的方式，将原集合的所有元素解包后加入新元素，生成全新的集合实例：

  {*hash_set, x}
  

• 方法2：使用集合的union方法
  调用原集合.union({新元素})，该方法会返回原集合与传入集合的并集，不会修改原集合：

  hash_set.union({x})
  

修改后的my_func2代码如下：

def my_func2(s, temp, i, n, hash_set):
    if i == n:
        print(temp)
        return
    
    for x in range(n):
        if x not in hash_set:
            # 二选一即可
            my_func2(s, temp + s[x], i+1, n, {*hash_set, x})
            # my_func2(s, temp + s[x], i+1, n, hash_set.union({x}))

string = 'aabc'
my_func2(string, '', 0, len(string), set())

这两种方法都不会修改原集合，每次递归都会创建独立的新集合，完全避免了递归栈中其他调用的状态被干扰。同时集合的in操作时间复杂度为O(1)，比列表的O(n)更高效，满足性能需求。

内容的提问来源于stack exchange，提问作者Rishab V Arun