C++でソート順のN番目のバイナリ文字列を効率的に求める方法

問題概要

この問題では、正の整数Nが与えられます。記号「a」と「b」のみを使用して生成できる無限の文字列リストを辞書順（辞書式順序）に並べたとき、そのN番目の文字列を見つけることが課題です。

文字列のリストは以下のように並んでいます。

a, b, aa, ab, ba, bb, aaa, aab, aba, …

例で問題を理解する

入力：N = 8
出力：aab

解法アプローチ

最も単純な解決策は、ループを使って文字列を先頭から順にすべて生成し、N番目の文字列を返す方法です。この方法でも正しい結果は得られますが、Nが大きな値になる場合には計算コストが膨大になり、効率的な解とは言えません。

そこで、より短時間で答えを導ける別のアプローチを紹介します。

効率的な解法の一つが、「相対インデックス（relative index）」を利用する方法です。長さLの文字列は2種類の記号から 2^L 通り生成できるという事実を活用します。まず、log2(N+1) の切り捨て値から目的の文字列の長さを求め、相対インデックスを次の式で計算します。

相対インデックス = N + 1 − 2^{floor(log2(N+1))}

この相対インデックスを2進数に変換し、各ビットを「0 → a」「1 → b」に対応させることで、目的の文字列を直接構築できます。これにより、全文字列を生成することなく O(log N) で答えを求められます。

実装例

以下は、この解法の動作を示すC++プログラムです。

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
string findBinString(ll n){
    ll len = (int)log2(n + 1);
    int ri = n + 1 - pow(2, len);
    ll i = 0;
    string binString = "";
    for (i = 0; i < len; i++) {
        binString += 'a';
    }
    i = 0;
    while (ri > 0) {
        if (ri % 2 == 1)
            binString[i] = 'b';
        ri /= 2;
        i++;
    }
    reverse(binString.begin(), binString.end());
    return binString;
}
int main(){
    ll n = 245;
    cout<<"The "<<n<<"-th binary string in sorted order is "<<findBinString(n);
    return 0;
}

出力

The 245-th binary string in sorted order is bbbabba