在生成數(shù)據(jù)的過程中，我們有時(shí)候需要基于已有的數(shù)據(jù)生成排列組合的序列，對此，我們需要編寫全排列算法生成序列，本文將分享本人編寫的遞歸實(shí)現(xiàn)的全排列算法，支持對任意類型的數(shù)據(jù)進(jìn)行生成全排列序列（不局限于數(shù)字）
全排列： 從n個(gè)不同元素中任取m（m≤n）個(gè)元素，按照一定的順序排列起來，叫做從n個(gè)不同元素中取出m個(gè)元素的一個(gè)排列。當(dāng)m=n時(shí)所有的排列情況叫全排列。
全排列數(shù)： f(n)=n!(定義0!=1)f(n)=n!(定義0!=1)
遞歸實(shí)現(xiàn)方法：
- 要求長度為n的序列的全排列序列：
- ①依次選取原始序列一個(gè)元素作為全排列序列結(jié)果的第一個(gè)元素
- ②遞歸調(diào)用全排列算法生成剩余n-1個(gè)元素的所有全排列序列
- ③將①的元素分別與②的每一個(gè)序列組合，即可得到長度為n的序列所有全排列序列
- ④遞歸結(jié)束條件：長度n=2的序列seq的有兩個(gè)全排列序列為[seq[0],seq[1]]和 [seq[1],seq[0]]

代碼

輸入：長度為n的序列，元素可以任何類型
輸出：輸入序列的所有全排列序列

def full_sort(seq: list):
    '''
    author: 淺若清風(fēng)cyf
    date: 2022/03/17
    全排列算法（遞歸）
    :param seq: 原始序列
    :return:
    '''
    results = []
    if len(seq) == 1:
        return seq
    elif len(seq) == 2:  # 遞歸返回終點(diǎn)
        return [[seq[0], seq[1]], [seq[1], seq[0]]]
    else:
        for i in seq:
            sub_seq = seq.copy()  # list類型為引用傳遞，此處需要使用copy()創(chuàng)建一個(gè)副本，避免修改原始list
            sub_seq.remove(i)
            tmp_result = full_sort(sub_seq)  # 獲取子列表的全排列
            for t in tmp_result:
                results.append([i] + t)
        return results

測試結(jié)果

測試樣例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('')

在這里插入圖片描述