ZeroJudge 解題筆記：i646. 排列組合-排列

作者：王一哲
日期：2025年11月23日


ZeroJudge 題目連結：i646. 排列組合-排列

解題想法

這題原來應該是要考用函式遞迴及回溯，但是在 Python 可以用 itertools.permutatinos 産生所有的排列，在 C++ 可以用 algorithm 函式庫的 next_permutation。

Python 程式碼

使用時間約為 12 ms，記憶體約為 3.1 MB，通過測試。

import sys

def perm(n, s):
    if len(s) == n:
        print(s)
        return 
    for i in range(n):
        c = chr(i + ord('a'))
        if c in s: continue
        perm(n, s+c)

for line in sys.stdin:
    n = int(line)
    if n == 0: break
    perm(n, "")

使用時間約為 7 ms，記憶體約為 3.5 MB，通過測試。

import sys
from itertools import permutations

result = []
lines = sys.stdin.readlines()
for line in lines:
    n = int(line)
    if n == 0: break
    chars = [chr(i + ord('a')) for i in range(n)]
    for perm in permutations(chars):
        s = "".join(perm)
        result.append(f"{s}\n")
sys.stdout.write("".join(result))

C++ 程式碼

使用時間約為 1 ms，記憶體約為 324 kB，通過測試。

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

void perm(int n, string s) {
    if ((int)s.size() == n) {
        cout << s << "\n";
        return;
    }
    for(int i=0; i<n; i++) {
        char c = char(i + 'a');
        if (s.find(c) != string::npos) continue;
        perm(n, s+c);
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n;
    while(cin >> n && n != 0) {
        string s = "";
        perm(n, s);
    }
    return 0;
}

使用時間約為 1 ms，記憶體約為 364 kB，通過測試。

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

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n;
    while(cin >> n && n != 0) {
        if (n == 0) break;
        string s = "";
        for(int i=0; i<n; i++) s += char(i + 'a');
        cout << s << "\n";
        while(next_permutation(s.begin(), s.end())) {
            cout << s << "\n";
        }
    }
    return 0;
}