使用 Python 及 C++ 産生重複數字的所有排列方式

作者：王一哲
日期：2025年8月30日

前言

由於最寫連續寫到好幾個題目，需要從測資讀取一列數字，再産生這列數字的所有排列方式，例如 d762. 10344 - 23 out of 5。我之前都是用 Python 的 itertools.permutations 偷懶，但是為了準備之後的課程，還是來研究一下如何用遞迴及回溯産生所有的排列方式。

Python itertools.permutations

這是一個效率很好的迭代器，官方說明書在此 itertools.permutations，通常會搭配 for 迴圈一起使用，語法為

for [産生的數組名稱] in itertools.permutations(可以迭代的物件):

例如要産生 [1, 2, 3, 2, 1] 的所有排列方式可以這樣寫

from itertools import permutations

nums = [1, 2, 3, 2, 1]
for perm in permutations(nums):
    print(*perm)

如果只考慮 5 個數字的排列方式，總共會有 $5! = 120$ 種，以上的程式碼會輸出 120 行。但是這裡面有不少重複的結果，如果只想輸出不重複的結果，可以再稍微修改一下程式碼，用集合記錄已經産生過的結果，這樣就只會輸出 30 行。

from itertools import permutations

nums = [1, 2, 3, 2, 1]
used = set()
for perm in permutations(nums):
    if perm in used: continue
    used.add(perm)
    print(*perm)

Python 回溯

這是一種常見的寫法，效果基本上與 itertools.permutations 相同，但是産生排列結果的順序有點不一樣。例如要産生 [1, 2, 3, 2, 1] 的所有排列方式可以這樣寫，共輸出 120 行。

def generate_permutations(arr):
    """ 産生 arr 所有的排列方式 """
    n = len(arr)
    perms = []
    
    def backtrack(start):
        if start == n:  # 遞迴出口
            perms.append(arr[:])  # 這裡一定要用 [:] 或是 .copy() 複製資料
            return
        for i in range(start, n):  # 掃過 arr[start] ~ arr[n-1]
            arr[start], arr[i] = arr[i], arr[start]  # 交換
            backtrack(start+1)  # 遞迴
            arr[start], arr[i] = arr[i], arr[start]  # 回溯
    # end of backtrack
    backtrack(0)  # 呼叫 backtrack，從索引值 0 開始
    return perms

nums = [1, 2, 3, 2, 1]
for perm in generate_permutations(nums):
    print(*perm)

如果只想輸出不重複的結果，可以再稍微修改一下程式碼，這樣就只會輸出 30 行。

def generate_permutations(arr):
    """ 産生 arr 所有的排列方式 """
    n = len(arr)
    perms = []
    used = set()
    
    def backtrack(start):
        if start == n:  # 遞迴出口
            row = tuple(arr)  # set 之中要用 tuple，不能用 list
            if row not in used:
                used.add(row)
                perms.append(row)
            return
        for i in range(start, n):  # 掃過 arr[start] ~ arr[n-1]
            arr[start], arr[i] = arr[i], arr[start]  # 交換
            backtrack(start+1)  # 遞迴
            arr[start], arr[i] = arr[i], arr[start]  # 回溯
    # end of backtrack
    backtrack(0)  # 呼叫 backtrack，從索引值 0 開始
    return perms

nums = [1, 2, 3, 2, 1]
cnt = 0
for perm in generate_permutations(nums):
    cnt += 1
    print(cnt, *perm)

C++ algorithm 函式庫的排列函式

C++ algorithm 函式庫有兩個好用的工具 next_permutation 及 prev_permutation，可以用來改變 array 或 vector 之中的資料排列方式，而且不會産生重複的結果。next_permutation 會將資料用更大的方式排列，prev_permutation 會將資料用更小的方式排列，通常會搭配 while 迴圈一起使用，直到沒有更大或更小的排列方式時停止運作。但如果原來的資料沒有經過排序，例如 nums = {1, 2, 3, 2, 1}，想要用 next_permutation 産生所有的排列方式，就要先將 nums 由小到大排序，而且搭配 do while 迴圈，先印出原來的資料，再用 next_permutation 改變資料順序。

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> nums = {1, 2, 3, 2, 1};
    sort(nums.begin(), nums.end());
    int cnt = 0;
    do {
        cnt++;
        printf("%d: ", cnt);
        for(int i=0; i<(int)nums.size()-1; i++) printf("%d ", nums[i]);
        printf("%d\n", nums.back());
    } while(next_permutation(nums.begin(), nums.end()));
    return 0;
}

如果想要用 prev_permutation 産生 nums = {1, 2, 3, 2, 1} 所有的排列方式，就要先將 nums 由大到小排序，而且搭配 do while 迴圈，先印出原來的資料，再用 prev_permutation 改變資料順序。

#include <cstdio>
#include <vector>
#include <algorithm>
#include <functional>  // for greater
using namespace std;

int main() {
    vector<int> nums = {1, 2, 3, 2, 1};
    sort(nums.begin(), nums.end(), greater<int> ());
    int cnt = 0;
    do {
        cnt++;
        printf("%d: ", cnt);
        for(int i=0; i<(int)nums.size()-1; i++) printf("%d ", nums[i]);
        printf("%d\n", nums.back());
    } while(prev_permutation(nums.begin(), nums.end()));
    return 0;
}

C++ 回溯

原則跟 Python 回溯版本一樣，例如要産生 {1, 2, 3, 2, 1} 的所有不重複的排列方式可以這樣寫，共輸出 30 行。

#include <cstdio>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

void backtrack(vector<vector<int>>& perms, vector<int>& arr, set<vector<int>>& used, int start) {
    int n = (int)arr.size();
    if (start == n) {
        if (used.find(arr) == used.end()) {
            used.insert(arr);
            perms.push_back(arr);
        }
        return;
    }
    for(int i=start; i<n; i++) {
        swap(arr[start], arr[i]);
        backtrack(perms, arr, used, start+1);
        swap(arr[start], arr[i]);
    }
}

void generate_permutations(vector<vector<int>>& perms, vector<int>& nums) {
    set<vector<int>> used;
    vector<int> arr (nums.begin(), nums.end());
    backtrack(perms, arr, used, 0);
}

int main() {
    vector<int> nums = {1, 2, 3, 2, 1};
    vector<vector<int>> perms;
    generate_permutations(perms, nums);
    int cnt = 0;
    for(auto perm : perms) {
        cnt++;
        printf("%d: ", cnt);
        for(int i=0; i<(int)perm.size()-1; i++) printf("%d ", perm[i]);
        printf("%d\n", perm.back());
    }
    return 0;
}