ZeroJudge 解題筆記：a469. 10063 - Knuth's Permutation

作者：王一哲
日期：2026年1月3日


ZeroJudge 題目連結：a469. 10063 - Knuth's Permutation

解題想法

題目的文字敘述不太容易理解，討論區這篇貼文的解釋比較詳細 https://zerojudge.tw/ShowThread?postid=18884&reply=18880#18884。寫一個自訂函式 solve，依照 Knuth's Permutation 的規則産生所有的排列方式。

Python 程式碼

使用時間約為 0.2 s，記憶體約為 33.7 MB，通過測試。

import sys

def solve(letters):  # 輸入字串，依照 Knuth's Permutation 的規則産生所有的排列方式
    perms = [letters[0]]  # 所有的排列方式，先放入 letters[0]
    for letter in letters[1:]:  # 依序讀取 letters[1] ~ letters[-1]
        new_perms = []  # 新的排列方式
        for perm in perms:  # 依序讀取 perms 每一項
            for i in range(len(perm) + 1):  # 依序找 i = 0 ~ len(perm) 的位置
                new_perm = perm[:i] + letter + perm[i:]  # 用字串切片，從左到右的位置組合新的排列方式
                new_perms.append(new_perm)  # new_perm 加入 new_perms
        perms = new_perms  # 更新 perms，每跑完一次 perms 中每一項長度加 1
    return perms  # 回傳 perms

for line in sys.stdin:
    perms = solve(line.strip())
    for perm in perms: print(perm)
    print()

C++ 程式碼

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

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

void solve(string letters) {
    string first = letters.substr(0, 1);
    vector<string> perms = {first};
    for(char letter : letters.substr(1)) {
        vector<string> new_perms;
        for(string perm : perms) {
            for(int i=0; i<=(int)perm.size(); i++) {
                string new_perm = perm.substr(0, i) + letter + perm.substr(i);
                new_perms.push_back(new_perm);
            }
        }
        perms = new_perms;
    }
    for(string perm : perms) cout << perm << "\n";
    cout << "\n";
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    string letters;
    while(cin >> letters) solve(letters);
    return 0;
}