C++で1回のスワップ操作により次に大きい数を求めるアルゴリズム

ある数 n が与えられたとき、その桁のうち任意の2桁を入れ替える（スワップする）ことで、元の数 n よりも大きい数を作ることを考えます。もし作ることができない場合は -1 を出力します。具体的な例を見てみましょう。

入力例：

12345

出力例：

12354

この例では、4と5の2桁を入れ替えることで、たった1回のスワップ操作でより大きい数を得ています。

アルゴリズムの考え方

• 数の各桁が降順（大きい順）に並んでいる場合、どの2桁を入れ替えてもより大きい数は作れないため、-1 を返します。
• 右側から走査し、末尾の桁よりも小さい値を持つ桁のインデックスを探します。
• 次に、見つかった桁よりも大きく、かつ候補の中で最小となる桁のインデックスを探します。
• これら2つの桁を入れ替えた結果を新しい数として返します。

C++での実装例

以下は、上記のアルゴリズムをC++で実装したコードです。

#include <bits/stdc++.h>
using namespace std;
string getNextHigherNumber(string num) {
    int len = num.size();
    int firstDigitIndex = -1;
    for (int i = len - 2; i >= 0; i--) {
        if (num[i] < num[len - 1]) {
            firstDigitIndex = i;
            break;
        }
    }
    if (firstDigitIndex == -1) {
        return "-1";
    }
    int secondDigitIndex = -1;
    for (int i = len - 1; i > firstDigitIndex; i--) {
        if (num[i] > num[firstDigitIndex]) {
            if (secondDigitIndex == -1 || num[i] <= num[secondDigitIndex]) {
                secondDigitIndex = i;
            }
        }
    }
    char temp = num[firstDigitIndex];
    num[firstDigitIndex] = num[secondDigitIndex];
    num[secondDigitIndex] = temp;
    return num;
}

int main() {
    string num = "12345";
    cout << "Given number: " << num << endl;
    cout << "Next higher number: " << getNextHigherNumber(num) << endl;
    return 0;
}

実行結果

上記のコードを実行すると、以下のような出力が得られます。

Given number: 12345
Next higher number: 12354

このように、末尾から条件に合う桁を見つけて適切な相手と入れ替えることで、効率的に「次に大きい数」を求めることができます。計算量は文字列の長さに対して線形時間 O(n) で済むため、大きな数値でも高速に処理できるのが特徴です。