Python遞歸生成全排列序列實操

更新時間：2022年04月15日 14:24:24 作者：淺若清風cyf?

這篇文章主要介紹了Python遞歸生成全排列序列實操,文章給予Python遞歸的相關(guān)資料展開對全排列序列的實現(xiàn)介紹，需要的小伙伴可以參考一下

前言

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

在這里插入圖片描述