C++ですべての順列が元の数以上となる自然数の個数を数える方法

自然数 num が与えられたとき、「桁をどのように並べ替えても元の数より小さくならない」自然数が num 以下にいくつ存在するかを求めるのがこの問題です。

問題の条件

• 扱うのは自然数のみとします。
• その数のすべての順列(桁の並べ替え)が、元の数と等しいかそれより大きくなければなりません。

例:num = 20 の場合

1から20までの数を順に調べてみましょう。

• 1〜9 は一桁の数なので、並べ替えようがなく常に条件を満たします。
• 2桁の数では、11 は 11=11、12 は並べ替えると 21(21 > 12)、13 は 31(31 > 13)…というように、19(91 > 19)までは反転した数が必ず元の数以上になります。一方、10 や 20 は「01」「02」というように並べ替えると元の数より小さくなるため条件を満たしません。
• したがって該当するのは 1〜9 と 11〜19 の計 18 個 となります。

入出力例

入力 − num = 10
出力 − 個数は 9

説明 − 1, 2, 3, 4, 5, 6, 7, 8, 9 の一桁の数だけが、どのように並べ替えても元の数と等しくなるため該当します。

入力 − num = 13
出力 − 個数は 12

説明 − 1〜9 に加えて、11(11=11)、12(並べ替えると 21)、13(並べ替えると 31)が該当します。

ポイント:条件を満たす数の特徴

すべての順列が元の数以上になるのは、各桁が左から右へ昇順(非減少)に並んでいる数だけです。桁を降順に並べ替えると必ず元の数以下になってしまうため、昇順に並んだ状態がその数の最小の並べ替えとなります。この性質を利用すると、下一桁が「直前の桁以上」となる数だけを体系的に生成でき、無駄な全探索を避けられます。

プログラムのアプローチ

• 数値 num を入力として受け取ります。
• max_size を 9 に設定します。一桁の数(1〜9)は必ず条件を満たすためです。
• i を 1 から max_size までループさせます。
• ループ内で list 型の変数を作成し、i が num 以下であればリストの末尾に追加してカウントを 1 増やします。
• リストの先頭から要素を取り出し(pop_front)、その下一桁から 9 までの各数字を連結した新しい数 temp を生成します。
• temp が num 以下であればリストの先頭に追加(push_front)してカウントを 1 増やします。これにより、桁が昇順に並ぶ数だけが次々と生成されます。
• 最終的なカウントを返して結果を出力します。

C++での実装例

#include<bits/stdc++.h>
using namespace std;
// すべての順列が元の数以上となる自然数を数える関数
void count(int num){
    int count = 0;
    int max_size = 9;
    for (int i = 1; i <= max_size; i++){
        list<int> lists;
        if (i <= num){
            // リストの末尾に要素を挿入
            lists.push_back(i);
            count = count + 1;
        }
        // リストの末尾からイテレータを開始
        for(auto iter = lists.end(); iter != lists.begin(); ++iter){
            int first_ele = lists.front();
            lists.pop_front();
            for (int next = first_ele%10; next <= 9; next++){
                int temp = first_ele*10 + next;
                if (temp <= num){
                    lists.push_front(temp);
                    count++;
                }
            }
        }
    }
    cout<<"count of num "<<num <<" is "<<count<<endl;
}
int main(){
    count(1);
    count(9);
    count(7);
    count(0);
    count(12);
    return 0;
}

出力

上記のコードを実行すると、次の出力が得られます。

count of num 1 is 1
count of num 9 is 9
count of num 7 is 7
count of num 0 is 0
count of num 12 is 11

まとめ

この問題は、全ての並べ替えを実際に試す代わりに「各桁が昇順に並ぶ数」という特徴に着目することで効率的に解けます。list を使って条件を満たす数を桁を伸ばしながら次々に生成し、num 以下のものだけをカウントするこの手法は、単純な全探索よりもはるかに少ない計算量で正確な答えを得られる点が大きな魅力です。