如何实现任意长度唯一元素列表的全排列（不使用itertools）

要实现任意长度唯一元素列表的全排列，递归是最直观的方案，核心逻辑很简单：

• 当列表只剩一个元素时，它本身就是唯一的排列
• 对于更长的列表，依次把每个元素作为排列的第一个元素，然后递归生成剩余元素的全排列，最后把当前元素拼到每个子排列的开头

下面是Python实现代码：

def permute(lst):
    # 基准情况：列表长度为1，直接返回包含自身的列表
    if len(lst) == 1:
        return [lst.copy()]
    
    result = []
    for i in range(len(lst)):
        # 取出当前要作为首项的元素
        current = lst[i]
        # 生成剩余元素的子列表
        remaining = lst[:i] + lst[i+1:]
        # 递归获取剩余元素的全排列
        for p in permute(remaining):
            # 把当前元素拼到子排列前面，加入结果集
            result.append([current] + p)
    
    return result

# 测试示例
test_list = ['a', 'b', 'c', 'd']
permutations = permute(test_list)
# 可以把每个排列转成字符串方便查看
for p in permutations:
    print(''.join(p))

代码解释 #

1. 基准条件：当输入列表长度为1时，直接返回包含该列表的列表，这是递归的终止点，避免无限递归。
2. 遍历每个元素：循环遍历列表中的每一个元素，将其作为当前排列的首元素。
3. 生成剩余元素列表：通过切片操作，移除当前选中的元素，得到剩余元素的子列表。
4. 递归调用：对剩余元素的子列表递归调用permute函数，得到所有子排列。
5. 拼接结果：将当前首元素与每个子排列拼接，加入最终的结果列表。

这个算法能适配任意长度的唯一元素列表，不需要依赖itertools.permutations，完全靠递归逻辑生成所有全排列。

内容的提问来源于stack exchange，提问作者monarch