Pythonで辞書式順序の最初のn個の数を生成するプログラム

はじめに

数値 n が与えられたとき、「辞書式順序（lexicographic order）」に従って並べ替えられた最初の n 個の数を求めることを考えます。辞書式順序とは、数値を文字列として扱い、左から1文字ずつ比較して並べる方式のことです。

例えば、入力が n = 15 の場合、出力は次のようになります。

[1, 10, 11, 12, 13, 14, 15, 2, 3, 4, 5, 6, 7, 8, 9]

これは通常の数値の大小順（1, 2, 3, …）ではなく、「1」の次に「10」「11」「12」と続く、文字列として比較したときの順序になっている点に注目してください。

解決アプローチ

この問題は、次の手順で解くことができます。

• 変数 count を 1 で初期化します
• 答えを格納するリスト ans を、count（=1）のみを含む状態で作成します
• ans の要素数が n 未満である間、以下を繰り返します
  • count を 10 倍します
  • count が n より大きい間、以下を繰り返します
    • count を 10 で割った商に更新します
    • count に 1 を加えます
    • count を 10 で割った余りが 0 である間、さらに count を 10 で割った商に更新します
  • count を ans の末尾に追加します
• 最後に ans を返します

実装例

以下がPythonでの実装例です。

class Solution:
    def solve(self, n):
        count = 1
        ans = [count]

        while len(ans) < n:
            count *= 10
            while count > n:
                count //= 10
                count += 1
                while count % 10 == 0:
                    count //= 10
            ans.append(count)
        return ans

ob = Solution()
n = 15
print(ob.solve(n))

入力

15

出力

[1, 10, 11, 12, 13, 14, 15, 2, 3, 4, 5, 6, 7, 8, 9]

アルゴリズムのポイント

このアルゴリズムの動きを簡単に整理すると、次のとおりです。

• まず 1 から始めて、可能な限り桁を増やしていきます（1 → 10 → 100 …）。これにより「1」の直後に来るべき「10」系の数を先に生成できます。
• count が n を超えたら、一度 10 で割って桁を戻し、1 を足すことで次の数へ進みます。
• 末尾が 0 の数（例：20、30）は辞書式順序の途中には現れないため、余りが 0 である限り桁を削り落とします。
• この操作を繰り返すことで、ソート処理なしに辞書式順序の数列を直接構築できます。

計算量

各ステップで定数回の演算しか行わないため、全体の時間計算量は O(n) です。n 個の数を生成してからソートする方法（O(n log n)）よりも効率的で、追加のメモリも結果リスト以外ほぼ不要です。