1からnまでの2進数を生成する興味深い方法：キューを使ったシンプルなアルゴリズム

ここでは、1からnまでの2進数を生成するための興味深い手法を紹介します。このアルゴリズムのポイントはキュー（queue）を活用するところにあります。

基本的な考え方は非常にシンプルです。まず、キューの初期状態として最初の2進数「1」を格納します。その後、以下の操作を繰り返します。

• キューの先頭から要素を取り出す（デキュー）
• 取り出した要素を出力する
• 先頭要素の末尾に「0」を付けたものをキューに挿入する
• 先頭要素の末尾に「1」を付けたものをキューに挿入する

この処理をn回繰り返すことで、1からnまでの2進表現が順番に得られます。それでは、具体的なアルゴリズムを見ていきましょう。

アルゴリズム

genBinaryNumbers(n)

Begin
    define empty queue.
    insert 1 into the queue
    while n is not 0, do
       delete element from queue and store it into s1
       print s1
       s2 := s1
       insert s1 by adding 0 after it into queue
       insert s1 by adding 1 after it into queue
       decrease n by 1
    done
End

C++による実装例

次に、C++のSTL（標準テンプレートライブラリ）のqueueを使用した実装例を示します。

#include <iostream>
#include <queue>
using namespace std;
void genBinaryNumbers(int n){
   queue<string> qu;
   qu.push("1");
   while(n != 0){
      string s1 = qu.front();
      qu.pop();
      cout << s1 << " ";
      string s2 = s1;
      qu.push(s1 + "0");
      qu.push(s1 + "1");
      n--;
   }
}
int main() {
   int n = 15;
   genBinaryNumbers(n);
}

実行結果

n = 15 の場合、プログラムを実行すると以下のような出力が得られます。

1 10 11 100 101 110 111 1000 1001 1010 1011 1100 1101 1110 1111

動作の仕組み

このアルゴリズムが正しく機能する理由は、FIFO（先入れ先出し）というキューの特性にあります。「1」から始めて、各要素に対して末尾に「0」と「1」を追加した2つの新しい2進数を順番に生成していくことで、自然と桁の小さい順（つまり数値の昇順）に2進数が並びます。

例えば、「1」を処理すると「10」と「11」が生成され、次に「10」を処理すると「100」と「101」が生成されます。このように、幅優先探索（BFS）と同じ発想で木構造を辿ることにより、効率的かつ直感的に連続する2進数列を構築できるのです。

時間計算量はO(n)、空間計算量もO(n)であり、ビット演算や整数から文字列への変換を繰り返す方法と比べても、非常にエレガントなアプローチだと言えるでしょう。