C++で数値の次に大きい順列を求めるプログラム

数値 n が与えられたとき、その桁を並び替えてできる「次に大きい順列」を求めます。n がすでに最大の順列（桁が降順に並んでいる状態）である場合は、最小の順列（昇順）へと折り返します。

例えば、入力が n = 319 の場合、出力は 391 になります。

解法のアプローチ

この問題は、C++ の標準ライブラリにある next_permutation と同じ考え方で解くことができます。右端から見て初めて昇順が崩れる位置（ピボット）を探し、ピボットより大きい数字のうち最小のものと交換した後、ピボットより右側を昇順に並べ替えることで、全体として「次に大きい」並びを実現します。具体的には、以下のステップで処理を組み立てます。

1. 数値を桁の配列に変換する（makeArray 関数）

• 配列 ret を定義します。
• x が 0 でない間、次の処理を繰り返します。
• ret の末尾に x mod 10（1 の位の数字）を追加します。
• x := x / 10 として桁を 1 つずらします。
• 最後に配列 ret を反転して返します。これで、元の数値と同じ桁順の配列が得られます。

2. 配列を数値に戻す（combine 関数）

• ret := 0 で初期化します。
• v の各要素 i について、ret := ret * 10、その後 ret := ret + i を実行します。
• ret を返します。

3. 入れ替え位置を見つける（getIndex 関数）

• ret := -1 で初期化します。
• i を配列 v のサイズから 1 まで減らしながら走査し、v[i] > v[i - 1] を満たす位置が見つかれば ret := i としてループを抜けます。
• ret が -1 でない場合（入れ替え位置が見つかった場合）は、以下の処理を行います。
• x := v[ret - 1] とします。
• idx := ret とします。
• j を ret + 1 から配列 v の末尾まで増やしながら、v[j] < v[idx] かつ v[j] > x を満たす j を探し、見つかれば idx := j で更新します。これは「x より大きい数字のうち最小のもの」を探す処理です。
• v[ret - 1] と v[idx] を交換します。

4. 全体の流れを組み立てる（solve 関数）

• 配列 v := makeArray(num) を作成します。
• idx := getIndex(v) を求めます。
• idx が -1 の場合（すでに最大の順列である場合）、配列 v 全体を昇順にソートします。
• それ以外の場合、v.begin() + idx 以降の部分のみを昇順にソートします。
• combine(v) を返します。

実装例

理解を深めるために、以下の実装例を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    vector<int> makeArray(int x) {
        vector<int> ret;
        while (x) {
            ret.push_back(x % 10);
            x /= 10;
        }
        reverse(ret.begin(), ret.end());
        return ret;
    }
    int combine(vector<int>& v) {
        int ret = 0;
        for (int i : v) {
            ret *= 10;
            ret += i;
        }
        return ret;
    }
    int getIndex(vector<int>& v) {
        int ret = -1;
        for (int i = v.size() - 1; i >= 1; i--) {
            if (v[i] > v[i - 1]) {
                ret = i;
                break;
            }
        }
        if (ret != -1) {
            int x = v[ret - 1];
            int idx = ret;
            for (int j = ret + 1; j < v.size(); j++) {
                if (v[j] < v[idx] && v[j] > x) {
                    idx = j;
                }
            }
            swap(v[ret - 1], v[idx]);
        }
        return ret;
    }
    int solve(int num) {
        vector<int> v = makeArray(num);
        int idx = getIndex(v);
        if (idx == -1) {
            sort(v.begin(), v.end());
        }
        else {
            sort(v.begin() + idx, v.end());
        }
        return combine(v);
    }
};
int solve(int n) {
    return (new Solution())->solve(n);
}
int main() {
    int n = 319;
    cout << solve(n);
}

入力

319

出力

391