n桁の非減少数の総数を求めるアルゴリズムとC++実装

非減少数とは

非減少数（non-decreasing number）とは、上位の桁から順に見て、どの桁も直前の桁より小さくない（＝各桁がひとつ前の桁以上になっている）数のことです。たとえば、111、112、123、789、569 などはすべて非減少数です。

この記事では、N 桁の数の中に非減少数がいくつ存在するかを、動的計画法（DP）を使って求めるアルゴリズムを解説します。

漸化式による定式化

count(n, d) を「長さ n で末尾の桁が d である非減少数の個数」と定義すると、次のような関係式が成り立ちます。

$$count(n,d)=\displaystyle\sum\limits_{i=0}^d count(n-1,i)\\total=\displaystyle\sum\limits_{d=0}^{9} count(n,d)$$

この式は、「長さ n・末尾が d の非減少数」は、直前の桁が 0〜d のいずれかである「長さ n−1 の非減少数」をつなげることで作れる、という考え方に基づいています。最終的な答えは、長さ n の数について末尾の桁ごとの個数（0〜9）をすべて合計した値になります。

入力と出力

入力:
桁数（例: 3）

出力:
非減少数の総数。この場合は 220。
非減少数の例: 111, 112, 123, 789, 569 など

アルゴリズム

countNumbers(n)

入力: 与えられた桁数 n。

出力: n 桁の非減少数の個数。

Begin
    サイズ (10 × n+1) の count 行列を定義し、すべて 0 で初期化する
    for i := 0 to 9, do
        count[i, 1] := 1        // 1桁の非減少数は各数字につき1つ
    done

    for digit := 0 to 9, do
        for len := 2 to n, do
            for x := 0 to digit, do
                count[digit, len] := count[digit, len] + count[x, len-1]
            done
        done
    done

    nonDecNum := 0
    for i := 0 to 9, do
        nonDecNum := nonDecNum + count[i, n]
    done

    return nonDecNum
End

C++での実装例

#include<iostream>
using namespace std;

long long int countNumbers(int n) {
    // count[i][j]: 末尾の数字が i で、長さ j の非減少数の個数
    long long int count[10][n+1];

    for(int i = 0; i<10; i++)
        for(int j = 0; j<n+1; j++)
            count[i][j] = 0;    // まずすべての要素を 0 で初期化

    for (int i = 0; i < 10; i++)    // 1桁の非減少数は各数字1つずつ
        count[i][1] = 1;

    for (int digit = 0; digit <= 9; digit++) {   // 末尾の数字 0〜9 それぞれについて
        for (int len = 2; len <= n; len++) {     // 長さ 2〜n の数を作る
            for (int x = 0; x <= digit; x++)
                count[digit][len] += count[x][len-1];   // 直前の桁 x ≤ digit の個数を加算
        }
    }

    long long int nonDecNum = 0;

    for (int i = 0; i < 10; i++)    // 末尾が 0〜9 のものをすべて合計
        nonDecNum += count[i][n];
    return nonDecNum;
}

int main() {
    int n = 3;
    cout << "Enter number of digits: "; cin >> n;
    cout << "Total non decreasing numbers: " << countNumbers(n);
}

実行結果

Enter number of digits: 3
Total non decreasing numbers: 220

補足：計算量と数学的な背景

このアルゴリズムの計算量は、三重ループのサイズから O(10 × n × 10)、すなわち桁数 n に対してほぼ線形の O(n) となります。大きな n でも高速に答えを求められるのが魅力です。

また、n 桁の非減少数の総数は、0〜9 の 10 種類の数字から重複を許して n 個を選ぶ並べ方の総数、すなわち重複組み合わせ H(10, n) ＝ C(n+9, 9) と一致します。実際、n ＝ 3 のときは C(12, 9) ＝ 220 となり、プログラムの出力とぴったり合致します。なお、このカウントでは先頭が 0 になる並び（例: 011、012 など）も含まれている点に注意してください。