配列やループを使わずにC言語で{1, 2, 3, … n}のすべての部分集合を出力する方法

正の整数 n が与えられたとき、配列やループを一切使用せずに、集合 {1, 2, 3, 4, … n} のすべての部分集合（サブセット）を出力することを目標とします。

例えば 3 が与えられた場合、集合 {1, 2, 3} のすべての部分集合、つまり {1 2 3}、{1 2}、{2 3}、{1 3}、{1}、{2}、{3}、{ } を出力します。

ただし、これらの出力にはループも配列も使用できません。したがって、この種の問題を配列やループなしで解決するには、再帰呼び出しを利用する方法が唯一の選択肢となります。

例

入力: 3
出力: { 1 2 3 }{ 1 2 }{ 1 3 }{ 1 }{ 2 3 }{ 2 }{ 3 }{ }
説明: 集合は {1 2 3} となり、そこからすべての部分集合を求めます
入力: 4
出力: { 1 2 3 4 }{ 1 2 3 }{ 1 2 4 }{ 1 2 }{ 1 3 4 }{ 1 3 }{ 1 4 }{ 1 }{ 2 3 4 }{ 2 3 }{ 2 4 }{ 2 }{ 3 4 }{ 3 }{ 4 }{ }

本問題を解くためのアプローチ

• num = 2^n − 1 から始めて 0 に至るまで順に処理を行います。
• num を n 桁の2進数表現として捉えます。
• 最左ビットは「1」を表し、2番目のビットは「2」、さらにその次は「3」というように、n 番目のビットが「n」に対応すると考えます。
• ビットが 1（セットされている）になっている場合、そのビットに対応する数値を出力します。
• num が 0 になるまで、すべての値に対して上記の手順を実行します。

それでは、簡単な例を使って、このアプローチがどのように機能するのか詳しく見ていきましょう。

入力 n = 3 の場合、num = 2^3 − 1 = 7 から処理が始まります。

7 の2進数表現 ⇒

対応する部分集合 ⇒

num から 1 を引きます。num = 6

6 の2進数表現 ⇒

対応する部分集合 ⇒

num から 1 を引きます。num = 5

5 の2進数表現 ⇒

対応する部分集合 ⇒

num から 1 を引きます。num = 4

4 の2進数表現 ⇒

対応する部分集合 ⇒

同様にして、num が 0 になるまで処理を繰り返し、すべての部分集合を出力します。

ポイントは、各ビットのオン・オフが「その要素を部分集合に含めるかどうか」を表している点です。ビットが立っていれば要素を含み、立っていなければ含めません。こうすることで、2^n 通りの組み合わせをすべて網羅できます。

アルゴリズム

開始
    ステップ1 → 関数 int subset(int bitn, int num, int num_of_bits) 内
    If bitn >= 0
      If (num & (1 << bitn)) != 0
         Print num_of_bits - bitn
         subset(bitn - 1, num, num_of_bits);
      Else
         Return 0
      Return 1
    ステップ2 → 関数 int printSubSets(int num_of_bits, int num) 内
       If (num >= 0)
          Print "{ "
          関数 subset(num_of_bits - 1, num, num_of_bits) を呼び出す
          Print "}"
          関数 printSubSets(num_of_bits, num - 1) を呼び出す
       Else
          Return 0
       Return 1
    ステップ3 → 関数 int main() 内
       int n = 4 を宣言・初期化する
       関数 printSubSets(n, (int) (pow(2, n)) -1) を呼び出す
終了

実装例（C言語）

#include <stdio.h>
#include <math.h>
// この関数は、num の2進数表現に対応する
// 部分集合を再帰的に出力します。
int subset(int bitn, int num, int num_of_bits) {
   if (bitn >= 0) {
      // 対応するビットが num 内で
      // セットされている場合のみ、
      // 部分集合の数値を出力します。
      if ((num & (1 << bitn)) != 0) {
         printf("%d ", num_of_bits - bitn);
      }
      // 次のビットを確認します
      subset(bitn - 1, num, num_of_bits);
   }
   else
      return 0;
      return 1;
}
// 部分集合を出力する関数
int printSubSets(int num_of_bits, int num) {
   if (num >= 0) {
      printf("{ ");
      // num の2進数表現に対応する
      // 部分集合を出力します。
      subset(num_of_bits - 1, num, num_of_bits);
      printf("}");
      // 次の部分集合を出力するために
      // 関数を再帰的に呼び出します。
      printSubSets(num_of_bits, num - 1);
   }
   else
      return 0;
      return 1;
}
// メインプログラム
int main() {
   int n = 4;
   printSubSets(n, (int) (pow(2, n)) -1);
}

出力結果

{ 1 2 3 4 }{ 1 2 3 }{ 1 2 4 }{ 1 2 }{ 1 3 4 }{ 1 3 }{ 1 4 }{ 1 }{ 2 3 4 }{ 2 3 }{ 2 4 }{ 2 }{ 3 4 }{ 3 }{ 4 }{ }