C++で同じ数字の組み合わせから「次に大きい数」を求める方法

この記事では、与えられた数値 N に対して、「同じ数字の組み合わせを使って表せる数のうち、N より大きい最小の数」を求める方法を解説します。これはいわゆる「次の順列(next permutation)」を求める問題として知られています。

問題を理解するための例

入力

N = "92534"

出力

92543

「92534」と同じ数字 {9, 2, 5, 3, 4} を使って作れる数の中で、92534 より大きい最小の数は 92543 です。

解法のアプローチ

次に大きい数を求めるためのシンプルな手順は以下の通りです。

• 数値を最下位桁から最上位桁へ向かって走査し、「現在の桁が左隣の桁より大きい」箇所が見つかった時点で停止します。この位置より右側は降順に並んでいます。

• 続いて、右側の部分から「基準となる桁(number[i-1])より大きく、かつ候補の中で最小の数字」を探し、基準の桁と交換します。

• 最後に、交換した位置より右側の部分配列を昇順にソートすれば、それが答えになります。

なお、走査しても条件を満たす箇所が見つからない場合(数字がすべて降順に並んでいる場合)は、それより大きい数が存在しないため「次の数は作れない」と判断します。

解法の動作を示すプログラム

例

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

void findNextGreater(char number[], int n) {
    int i, j;
    // 最下位桁から走査し、number[i] > number[i-1] となる位置を探す
    for (i = n-1; i > 0; i--)
        if (number[i] > number[i-1])
            break;
    // 見つからなければ次の数は作れない
    if (i == 0) {
        cout<<"Next number is not possible";
        return;
    }
    int x = number[i-1], smallest = i;
    // x より大きく、かつ最小の数字を探す
    for (j = i+1; j < n; j++)
        if (number[j] > x && number[j] < number[smallest])
            smallest = j;
    // 見つけた数字と交換
    char temp = number[smallest];
    number[smallest] = number[i-1];
    number[i-1] = temp;
    // 残りの部分を昇順ソート
    sort(number + i, number + n);
    cout<<number;
    return;
}

int main(){
    char number[] = "92534";
    int n = strlen(number);
    cout<<"The next number with same set of digits is ";
    findNextGreater(number, n);
    return 0;
}

出力

The next number with same set of digits is 92543

計算量について

このアルゴリズムの計算量は O(n log n) です(末尾のソート部分が支配的)。桁の走査や交換そのものは O(n) で行えるため、非常に効率的な手法といえます。