前半と後半のビット合計が等しいn桁の2進数をすべて生成する方法

本記事では、指定された桁数 n に対して、「2進数を前半と後半に分割したとき、両方のビットの合計が等しくなる」ようなすべての2進数を生成する方法を解説します。

例えば「100001」という6桁の2進数を見てみましょう。前半は「100」、後半は「001」であり、どちらもビットの合計が1で等しいため、この数は条件を満たします。以下では、このような性質を持つすべての2進数を効率よく列挙するアルゴリズムを紹介します。

アルゴリズムの基本アイデア

再帰関数 genAllBinEqualSumHalf(n, left, right, diff) を使用します。left と right は最初は空文字列で、diff には左半分と右半分のビット合計の差が格納されます。

• 左右へ同時に1桁ずつ追加： 再帰の各ステップで、left の末尾と right の末尾にビットを1つずつ追加し、残り桁数を2減らします。
• 差の管理： left に「1」・right に「0」を追加すると差は1増え、left に「0」・right に「1」を追加すると差は1減ります。同じビットを両側に追加した場合は差は変化しません。
• 枝刈り条件： 残り桁数では最大でもその桁数分しか差を埋められないため、2 * |diff| <= n を満たさない場合は探索を打ち切ります。これにより無駄な再帰を大幅に削減できます。
• 先頭の0を除外： left が空のとき（最初の呼び出し時）は「0」で始まるケースをスキップし、先頭が1となる数だけを生成します。

擬似コード

Begin
    if n == 0 then
        if diff == 0 then
            print left + right
        return
    if n == 1 then
        if diff == 0 then
            print left + "0" + right
            print left + "1" + right
        return
    if 2 * |diff| <= n then
        if left is not empty then
            genAllBinEqualSumHalf(n-2, left + "0", right + "0", diff)
            genAllBinEqualSumHalf(n-2, left + "0", right + "1", diff - 1)
        genAllBinEqualSumHalf(n-2, left + "1", right + "0", diff + 1)
        genAllBinEqualSumHalf(n-2, left + "1", right + "1", diff)
End

C++による実装例

#include <bits/stdc++.h>
using namespace std;

// leftとrightの文字列を構築し、diは左右のビット合計の差を保持する
void genAllBinEqualSumHalf(int n, string left="", string right="", int di=0) {
    if (n == 0) { // 残り桁数が0のとき
        if (di == 0) // 差が0なら、leftとrightを連結して出力
            cout << left + right << " ";
        return;
    }
    if (n == 1) { // 残り1桁の場合
        if (di == 0) { // 差が0なら、中央に0を入れたものと1を入れたものを出力
            cout << left + "0" + right << " ";
            cout << left + "1" + right << " ";
        }
        return;
    }
    if ((2 * abs(di) <= n)) {
        if (left != ""){ // 先頭が0で始まる数は生成しない
            genAllBinEqualSumHalf(n-2, left+"0", right+"0", di);
            // 左右に0を追加（差は変化なし）
            genAllBinEqualSumHalf(n-2, left+"0", right+"1", di-1);
            // 左に0・右に1を追加（差が1減る）
        }
        genAllBinEqualSumHalf(n-2, left+"1", right+"0", di+1); // 左に1・右に0を追加（差が1増える）
        genAllBinEqualSumHalf(n-2, left+"1", right+"1", di);   // 左右に1を追加（差は変化なし）
    }
}

int main() {
    int n = 6;
    genAllBinEqualSumHalf(n);
}

実行結果

n = 6 の場合の出力は次のとおりです。

100001
100010
101011
110011
100100
101101
101110
110101
110110
111111

例えば「100010」は前半「100」（合計1）、後半「010」（合計1）となっており、「111111」は前半「111」（合計3）、後半「111」（合計3）となっており、いずれも条件を満たしていることが確認できます。なお、n が奇数の場合は中央の1桁がどちらの半分にも属さないため、n == 1 の分岐で中央のビットに0と1の両方を入れた2通りが出力される仕組みになっています。