ACM POJ 1146 ID Codes：下一字典序排列算法完整解析與 C++ 實作

題目大意

輸入一個字串（數字/字母），輸出其下一個字典序排列。若不存在（已為最大排列），輸出 No Successor。輸入 # 結束。

字典序下一排列算法（標準庫 next_permutation 邏輯）

1. 從右向左找第一個 a[i] < a[i+1] 的位置 i（樞軸）
2. 若不存在 → 已為最大排列，無後繼
3. 從右向左找第一個 a[j] > a[i] 的位置 j
4. 交換 a[i] 和 a[j]
5. 將 i+1 到末尾的子序列逆序（變為最小排列）

完整 C++ 實作

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

void printArr(int a[], int n) {
    for (int i = 1; i <= n; ++i) printf("%c", a[i] + '0');
    printf("\n");
}

int main() {
    char str[100];
    int a[100];
    while (scanf("%s", str) && strcmp(str, "#") != 0) {
        int n = strlen(str);
        for (int i = 1; i <= n; ++i) a[i] = str[i-1] - '0';

        int i = n - 1;
        while (i > 0 && a[i] >= a[i+1]) --i; // 步驟 1

        if (i == 0) {
            puts("No Successor");
            continue;
        }

        int j = n;
        while (a[j] <= a[i]) --j; // 步驟 3

        swap(a[i], a[j]);         // 步驟 4
        reverse(a + i + 1, a + n + 1); // 步驟 5

        printArr(a, n);
    }
    return 0;
}

標準庫一行解法

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

int main() {
    string s;
    while (cin >> s && s != "#") {
        if (next_permutation(s.begin(), s.end()))
            cout << s << endl;
        else
            cout << "No Successor" << endl;
    }
    return 0;
}

複雜度分析

• 時間：O(n)，單次掃描 + 逆序
• 空間：O(1) 原地修改

關鍵細節

1. 字串可能含字母，用 char 直接比較 ASCII 碼即可
2. 逆序用 reverse 或雙指針交換
3. 輸入以 # 單獨一行結束
4. 輸出格式：每行一個結果，無多餘空格

測試範例

輸入：
123
321
abc
cba
#

輸出：
132
No Successor
acb
No Successor

總結

「找樞軸、換後繼、翻尾部」是下一排列的通用模板。面試/競賽中手寫版展示演算法理解，工程中優先用 std::next_permutation（支援任意雙向迭代器、自定義比較器）。