ZeroJudge 解題筆記：e446. 排列生成

作者：王一哲
日期：2025年9月21日


ZeroJudge 題目連結：e446. 排列生成

解題想法

這題不論用 Python 還是 C++ 都可以用遞迴窮舉所有的排列方式。在 Python 也可以用 itertools.permutaions，在 C++ 也可以用 next_permutation。但主要的困難之處是輸出速度，要加速才能過關。

Python 程式碼

窮舉，用 print 輸出，超時。

def solve(arr, n, used):
    if len(arr) == n:
        print(*arr)
        return
    for i in range(1, n+1):
        if i in used: continue
        used.add(i)
        arr.append(i)
        solve(arr, n, used)
        used.remove(i)
        arr.pop()
    return

solve([], int(input()), set())

窮舉，用 sys.stdout.write 輸出，超時。

import sys

def solve(arr, n, used):
    if len(arr) == n:
        s = " ".join(map(str, arr)) + "\n"
        sys.stdout.write(s)
        return
    for i in range(1, n+1):
        if i in used: continue
        used.add(i)
        arr.append(i)
        solve(arr, n, used)
        used.remove(i)
        arr.pop()
    return

solve([], int(sys.stdin.readline()), set())

用 itertools.permutations，用 sys.stdout.write 最後再一次輸出所有結果，最後一筆測資超出記憶體上限。

import sys, itertools

result = []
n = int(sys.stdin.readline())
nums = list(range(1, n+1))
for perm in itertools.permutations(nums):
    s = " ".join(map(str, perm))
    result.append(f"{s}\n")
sys.stdout.write("".join(result))

用 itertools.permutations，用 sys.stdout.write 逐行輸出結果。使用時間約為 12.3 s，記憶體約為 3.4 MB，通過測試。

import sys, itertools

n = int(sys.stdin.readline())
nums = list(range(1, n+1))
for perm in itertools.permutations(nums):
    s = " ".join(map(str, perm)) + "\n"
    sys.stdout.write(s)

C++ 程式碼

使用時間約為 9.3 s，記憶體約為 344 kB，通過測試。

#include <iostream>
#include <vector>
#include <set>
using namespace std;

int N;
void perm(int depth, int maxDepth, vector<int>& nums, set<int>& tested) {
    if (depth == maxDepth) {
        for(int i=0; i<(int)nums.size(); i++)
            cout << nums[i] << " \n"[i == (int)nums.size()-1];
        return;
    }
    for(int i=1; i<=N; i++) {
        if (tested.count(i) == 1) continue;
        tested.insert(i);
        nums.push_back(i);
        perm(depth+1, maxDepth, nums, tested);
        tested.erase(i);
        nums.pop_back();
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> N;
    vector<int> nums;
    set<int> tested;
    perm(0, N, nums, tested);
    return 0;
}

使用時間約為 7.8 s，記憶體約為 352 kB，通過測試。

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int N; cin >> N;
    int nums[N];
    for(int i=0; i<N; i++) {
        nums[i] = i+1;
        cout << i+1 << " \n"[i == N-1];
    }
    while(next_permutation(nums, nums+N)) {
        for(int i=0; i<N; i++)
            cout << nums[i] << " \n"[i == N-1];
    }
    return 0;
}