2^n 通りのbit全探索を m^n 通りの深さ優先探索に一般化する

　以前の記事で bit 全探索を利用して冪集合を作った。

jnsato.hateblo.jp

　これは任意の有限集合の各要素について、部分集合に含めるか含めないかを表すフラグの組み合わせを総当たりする方法であった。各要素が 0 or 1 の二元のいずれかに振り分けられるため、 2ⁿ 通りの組み合わせが存在する。つまり、冪集合を作成するアルゴリズムとしてのみならず、各元が2通りの値を持ちうるすべてのパターンを列挙するのにも利用できる。そう考えるといくぶん実用ではないだろうか？

　しかしそうなるとおのずと、では各元が3通りの値を取りうるときは？　いっそそれ以上の可能性があるときは？　と一般化してみたくなる。そこでこの記事では、濃度 n の集合の各要素が m 個の値を取りうるとして、その部分集合をすべて列挙するようなアルゴリズムを考える。 mⁿ 個の部分集合が導かれることになる。

　このとき、bit全探索は一度すっかり忘れてしまった方がいい。bit全探索は、 2ⁿ 通りを列挙するという目的と、二進数のビット演算という手段がたまたま幸運な合致をしてくれていたおかげで使えたテクニックであり、 mⁿ ( m ≠ 2 ) には適用できない。基数変換して比較する、というのは、少なくとも m が 10 を超えうる限り、整数ではなく文字列で実装しなければならないし、ビット演算やシフト演算まで実装し直さなければならないのはさすがに腰が引ける。

　基本に戻って、シンプルに全探索することを考える。深さ優先探索で実装してみる。

#include<iostream>
#include<vector>
using namespace std;

void dfs(vector<int> &a, int m, int n) {
  if (a.size() == n) {
    for (int i : a) cout << i << " ";
    cout << endl;
    return;
  }

  for (int i = 1; i <= m; i++) {
    a.push_back(i);
    dfs(a, m, n);
    a.pop_back();
  }
}

int main() {
  vector<int> a;
  int m = 3, n = 5;
  dfs(a, m, n);
  return 0;
}

　もちろん m = 2 とすれば、これは bit 全探索と同じ結果を導く。