Cプログラムで同じ個数の1と0を持つ「次に大きい数」の2進表現を求める方法

ある数 n の2進表現が与えられたとき、「n より大きい数の中で最小のものであり、かつ0と1の個数が元の数と同じである」という条件を満たす数の2進表現を求めることを考えます。例えば、入力が 1011（10進数で11）であれば、出力は 1101（10進数で13）になります。この問題は、順列生成でおなじみの「次の順列（next permutation）」の考え方を応用することで効率よく解くことができます。それでは、具体的なアルゴリズムを見ていきましょう。

アルゴリズム

nextBin(bin) の処理手順は以下の通りです。

Begin
    len := 文字列 bin の長さ
    for i in range len-2, down to 1, do
        if bin[i] が '0' かつ bin[i+1] が '1' ならば
            bin[i] と bin[i+1] を入れ替える
            break
        end if
    done
    if i = 0 ならば変更は不要、return
    otherwise j := i + 2, k := len – 1
    while j < k, do
        if bin[j] が '1' かつ bin[k] が '0' ならば
            bin[j] と bin[k] を入れ替える
            j と k を更新する
        else if bin[i] が '0' ならば
            break
        else
            j を増やす
        end if
    done
    return bin
End

このアルゴリズムでは、まず右側から走査して「0の直後に1が来ている箇所」を探し、その2文字を入れ替えます。これにより数値が確実に大きくなります。その後、入れ替えた位置より右側の部分について、1をできるだけ左へ、0をできるだけ右へ集めることで、条件を満たす最小の数を作り上げます。

実装例

#include <iostream>
using namespace std;
string nextBinary(string bin) {
    int len = bin.size();
    int i;
    for (int i=len-2; i>=1; i--) {
        if (bin[i] == '0' && bin[i+1] == '1') {
            char ch = bin[i];
            bin[i] = bin[i+1];
            bin[i+1] = ch;
            break;
        }
    }
    if (i == 0)
    "No greater number is present";
    int j = i+2, k = len-1;
    while (j < k) {
        if (bin[j] == '1' && bin[k] == '0') {
            char ch = bin[j];
            bin[j] = bin[k];
            bin[k] = ch;
            j++;
            k--;
        }
        else if (bin[i] == '0')
            break;
        else
            j++;
    }
    return bin;
}
int main() {
    string bin = "1011";
    cout << "Binary value of next greater number = " << nextBinary(bin);
}

このコードでは、まず文字列の後方から走査して入れ替えポイントを特定し、続いて残りの部分を両端から調べながら1と0を並べ替えています。これにより、0と1の総数を保ったまま、元の数よりひとつだけ大きい2進数が得られます。

出力

Binary value of next greater number = 1101

入力 1011 に対して、同じく1が3個・0が1個という構成を保ちながら、より大きい最小の数 1101 が出力されていることが確認できます。