JavaScriptで辞書式順序に並んだ最初のn個の自然数シーケンスを生成する方法

問題

数値 n を引数として受け取り、最初の n 個の自然数を含む配列を返す JavaScript 関数を作成することを考えます。

ただし、ひとつだけ条件があります。それは、数値を辞書式順序（lexicographical order）で並べるという点です。辞書式順序とは、数値を文字列として比較したときの並び順のことで、たとえば「1」から始まるすべての数値は、「2」や「3」などから始まる数値よりも必ず前に来なければなりません。

そのため、通常の数値の大小順序とは異なり、「10」「11」「12」…といった数値は「2」よりも先に並ぶことになります。

コード例

以下がその実装コードです。

const num = 24;
const buildLexicographically = (num = 1) => {
   const res = [];
   const curr = num >= 9 ? 9 : num;
   for (let i = 1; i <= curr; i++) {
      res.push(i);
      for (let j = i * 10; j <= num; j++) {
         res.push(j);
         if (j % 10 === 9) {
            break;
         }
      }
   };
   return res;
};
console.log(buildLexicographically(num));

出力

コンソールには次のように出力されます。

[
   1, 10, 11, 12, 13, 14, 15, 16,
   17, 18, 19, 2, 20, 21, 22, 23,
   24, 3, 4, 5, 6, 7, 8, 9
]

アルゴリズムの解説

このコードがどのようにして辞書式順序を実現しているのか、ステップごとに見ていきましょう。

1. 先頭の桁ごとにグループ化する

外側のループでは、先頭の桁になりうる 1 から 9 までの数字を順番に処理します。変数 curr は、n が 9 未満の場合に備えてループの上限を n に制限する役割を果たしています。

2. 同じ先頭桁を持つ数を列挙する

内側のループでは、現在の先頭桁 i の 10 倍（つまり「i0」の形になる数）から開始し、n を超えない範囲で 1 ずつ増やしながら数値を配列へ追加していきます。j % 10 === 9 になった時点で break することで、次の先頭桁に進む前にそのブロックの列挙を終了させます。

この処理により、たとえば先頭が「1」の数（1, 10, 11, …, 19）がすべて揃った後で初めて「2」が登場するため、最終的な配列は完全な辞書式順序になります。

計算量について

各数値は配列にちょうど一度だけ追加されるため、このアルゴリズムの時間計算量は O(n) と非常に効率的です。さらに、事前にソート処理を行う必要がない点も大きなメリットといえます。