Python递归实现全排列算法详解与代码示例

陆景行

发布时间：2026-10-15 | 4人浏览过

原创

本文详细介绍如何使用Python递归算法生成任意类型数据的全排列序列。文章解析了全排列的数学定义与递归逻辑，提供了完整的Python代码实现，并通过整数与字符串两种测试样例验证了算法的有效性。该方法支持对任意长度和类型的序列进行全排列处理，适用于需要生成组合数据的技术场景。

前言

在数据处理过程中，经常需要基于现有数据生成排列组合序列。为此，我们需要编写全排列算法来生成这些序列。本文将分享一种基于递归实现的全排列算法，该算法支持对任意类型的数据生成全排列序列，并不局限于数字类型。
全排列的定义是：从n个不同元素中任取m（m≤n）个元素，按照一定的顺序排列起来，称为从n个不同元素中取出m个元素的一个排列。当取出的元素个数m等于总元素个数n时，所有的排列情况被称为全排列。
全排列的数量计算公式为：f(n)=n!（其中定义0!=1）。
递归实现方法：
- 若要生成长度为n的序列的所有全排列，需遵循以下逻辑：
- 第一步，依次选取原始序列中的一个元素，作为全排列结果序列的第一个元素。
- 第二步，递归调用全排列算法，生成剩余n-1个元素的所有全排列序列。
- 第三步，将第一步选取的元素分别与第二步生成的每一个子序列进行组合，从而得到长度为n的序列的所有全排列结果。
- 第四步，设定递归结束条件：当序列长度n=2时，该序列有两个全排列序列，分别为[seq[0],seq[1]]和[seq[1],seq[0]]。

代码

输入参数为长度为n的序列，序列中的元素可以是任何类型。
输出结果为输入序列的所有全排列序列列表。

def full_sort(seq: list):
    '''
    author: 浅若清风cyf
    date: 2022/03/17
    全排列算法（递归）
    :param seq: 原始序列
    :return:
    '''
    results = []
    if len(seq) == 1:
        return seq
    elif len(seq) == 2:  # 递归返回终点
        return [[seq[0], seq[1]], [seq[1], seq[0]]]
    else:
        for i in seq:
            sub_seq = seq.copy()  # list类型为引用传递，此处需要使用copy()创建一个副本，避免修改原始list
            sub_seq.remove(i)
            tmp_result = full_sort(sub_seq)  # 获取子列表的全排列
            for t in tmp_result:
                results.append([i] + t)
        return results

测试结果

测试样例1

if __name__ == '__main__':
    res = full_sort([1, 2, 3, 4])
    n = 0
    for i in res:
        print(i, end=' ')
        n += 1
        if n % 5 == 0:
            n = n % 5
            print('')

测试样例2

    res = full_sort(['Apple', 'XiaoMi', 'HuaWei', 'OPPO'])
    n = 0
    for i in res:
        print(i, end=' ')
        n += 1
        if n % 5 == 0:
            n = n % 5
            print('')