如何在 Python 中產生列表的所有排列

你可以使用 Python 標準函式庫產生列表的排列；若需要自訂流程，也可以選擇遞迴或迭代演算法。排列是對選定元素進行排序後得到的結果；與組合不同，排列會考慮元素順序。結果數量會按階乘級增長，因此只有輸入規模不大時，列出所有順序才切實可行。

使用 itertools 函式庫

大多數情況下，使用 itertools.permutations 即可。它會傳回由元組組成的迭代器，讓你逐一處理結果，而不必立即建立完整列表。預設的 r 值等於輸入長度，因此每個結果都會使用所有元素。以下範例中的 r=2 會選出長度為二的有序排列，而迴圈則會依序處理長度一到三的排列。

輸入列表 [1, 2, 3] 時，程式會印出：

from itertools import permutations

data = [1, 2, 3]
print("full:", list(permutations(data)))
print("length 2:", list(permutations(data, r=2)))
print("lengths 1 to 3:")
for r in range(1, len(data) + 1):
    print(r, list(permutations(data, r)))

full: [(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]
length 2: [(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]
lengths 1 to 3:
1 [(1,), (2,), (3,)]
2 [(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]
3 [(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]

r 引數會設定每個元組包含的項目數。如上所示，若要產生所有非空長度的排列，請從 1 到輸入長度逐一呼叫函式。itertools.permutations 會依元素所在的位置處理資料：如果輸入中有相同值，不同位置所形成的結果元組仍可能完全相同。

如需查看函式的完整簽章與行為，請參閱 Python 官方 itertools 說明文件。

使用遞迴函式產生排列

遞迴解法會依序選取每個項目，再將它放到剩餘項目的每種排列之前。基本情況會傳回只含一個空排列的列表；這樣的設計可讓建構流程適用於任何輸入長度，包括零。此版本傳回的是列表而非元組，適合用來學習或自訂排列的建構方式。

def permute(data):
    if not data:
        return [[]]

    result = []
    for index, item in enumerate(data):
        remaining = data[:index] + data[index + 1:]
        for tail in permute(remaining):
            result.append([item] + tail)
    return result

print(permute([1, 2, 3]))

[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

每次遞迴呼叫都會移除一個位置，因此剩餘輸入會逐漸縮小，直到到達基本情況。不同位置上的重複值仍可能產生內容相同的列表。這個實作會儲存完整結果，也會進行許多次遞迴呼叫，因此較適合用於學習或小型輸入；若不需要自訂建構流程，請使用標準函式庫的迭代器。

以迭代方式產生排列

你也可以把每個新項目插入目前已收集的部分排列中的每個位置，逐步建構結果。列表一開始只包含一個空排列；每處理一個新項目，結果數量就會乘上截至該步已處理的項目數：第一個項目有一個插入位置，第二個有兩個，第三個有三個，依此類推。這種方法不需要遞迴呼叫，但仍會儲存所有結果。

def iterative_permute(data):
    results = [[]]
    for item in data:
        next_results = []
        for ordering in results:
            for index in range(len(ordering) + 1):
                next_results.append(ordering[:index] + [item] + ordering[index:])
        results = next_results
    return results

print(iterative_permute([1, 2, 3]))

[[3, 2, 1], [2, 3, 1], [2, 1, 3], [3, 1, 2], [1, 3, 2], [1, 2, 3]]

插入順序會決定此方法傳回結果的先後次序，但不會改變它產生的排列集合。若逐步建構的方式適合你的需求，可以選用此方法；同時也要考量保留完整結果所需的記憶體。

結論

若要簡潔地逐一取得排列，請使用 itertools.permutations，並在需要特定長度時設定 r。若要自訂或學習排列的建構方式，則可使用遞迴或迭代插入法。當長度為 n 且各位置均視為不同時，完整排列共有 n! 種，因此處理時間以及將結果全部存入記憶體所需的空間都會快速增加。若輸入較大，請按需逐一處理迭代器，或只產生問題實際需要的長度與選取方式。

常見問題

1. 什麼是排列？
   排列是依序排列選定項目所得的結果。例如，[1, 2] 和 [2, 1] 是不同的排列，因為順序不同。

2. itertools.permutations 如何運作？
   它會從輸入可迭代物件中產生長度為 r 的元組。若省略 r，就會使用完整輸入長度。此函式會以惰性方式產生結果，但若將迭代器轉成列表，所有結果都會存入記憶體。

3. 輸入包含重複值時會怎樣？
   函式會依位置而非值是否相等來處理項目，因此重複的輸入值可能產生內容相同的元組。若元組中的元素可雜湊，全部產生後可以轉成集合以移除重複元組，但這不會避免重複結果在產生過程中被計算。若要避免重複工作，請使用會在每一步略過相同選項的演算法。

4. 排列有多少種？
   若有 n 個不同的位置，完整排列共有 n! 種。若只選取 r 個位置，排列數量為 n! / (n - r)!。

5. 輸入最多可以有多大？
   沒有適用於所有電腦與任務的固定大小上限。階乘級的結果數量可能讓中等大小的輸入也變得耗時，而儲存所有結果會使用大量記憶體。若不需要一次取得所有完整排列，請優先採用惰性迭代，或設定較小的 r。