【JavaScript】同じ数字の並び替えで作れる「ちょうど大きい数」を見つける方法

問題

数値 num を唯一の引数として受け取るJavaScript関数を作成する必要があります。

この関数が返すべきのは、入力された数値とまったく同じ数字だけ（すべての桁を使い切り、余分な数字を含まない）で構成され、入力値よりちょうど一つ大きい数です。

そのような数が存在しない場合は -1 を返します。

例

const num = 5656;

この場合の出力は以下のようになります。

const output = 5665;

出力の解説

5665 は 5656 と同じ数字（5、6、5、6）だけで構成されており、5656 より大きい数の中で最小のものであるためです。

アプローチ1：全探索（シンプルな方法）

最も直感的な方法は、入力値より1大きい数から順に調べ、同じ数字で構成されているかを確認していくことです。ここで便利な性質として、「入力の数字を降順に並べ替えたもの」が同じ数字で作れる最大の数になるため、これを探索の上限として利用できます。

const num = 5656;
const justBigger = (num) => {
    const sorted = num => ('' + num).split('').sort((a, b) => b - a);
    const max = +sorted(num).join('')
    for (let i = num + 1; i <= max; i++) {
        if (max === +sorted(i).join('')){
            return i;
        }
    };
    return -1;
}
console.log(justBigger(num));

出力

5665

このコードでは、まず各数値を文字列化して桁ごとに分割し、降順ソート後に再結合しています。入力値から最大値まで1ずつ増やしながら、同じ並び替え結果になる最初の数を返します。

ただし、この方法は桁数が増えると組み合わせの総数が爆発的に増えるため、処理が非常に遅くなるという欠点があります。

アプローチ2：次の順列アルゴリズム（効率的な方法）

桁数が多いケースでは、「次の順列」を求めるアルゴリズムを使うことで大幅に高速化できます。手順は以下の通りです。

1. 右端から走査し、初めて「左の桁 < 右の桁」となる位置（ピボット）を見つけます。
2. ピボットが存在しない場合、数字全体が降順に並んでいるため、より大きい数は作れません。-1 を返します。
3. ピボットより右側にある桁のうち、ピボットより大きい最小の桁を見つけてピボットと交換します。
4. ピボットより右側の部分を昇順に並べ替えて完成です。

const nextBigger = (num) => {
    const digits = ('' + num).split('');
    let i = digits.length - 2;

    // ピボットを探す
    while (i >= 0 && digits[i] >= digits[i + 1]) {
        i--;
    }
    if (i < 0) return -1;

    // ピボットより大きい最小の桁を探す
    let j = digits.length - 1;
    while (digits[j] <= digits[i]) {
        j--;
    }

    // ピボットと交換
    [digits[i], digits[j]] = [digits[j], digits[i]];

    // 右側を昇順に並べ替える
    const result = digits.slice(0, i + 1).concat(digits.slice(i + 1).sort());
    return +result.join('');
};

console.log(nextBigger(5656)); // 5665
console.log(nextBigger(21));   // -1
console.log(nextBigger(123));  // 132

まとめ

全探索による方法は実装が簡単ですが、計算量が桁数に対して指数的に増加します。一方、次の順列アルゴリズムを使えば O(n log n)（n は桁数）程度で求められるため、実用的な場面では後者を選ぶのが賢明です。どちらのコードも、同じ数字だけで構成される「ちょうど大きい数」を正しく返し、存在しない場合には -1 を返します。