XORベクトル空間のアルゴリズムとその正当性
はじめに
自然数全体の集合 は、以下のように和とスカラー倍を定めることにより、体 上のベクトル空間と見なせます。このベクトル空間を と書きます。
- 和は、bitwiseのXOR演算(以下では単に と書く)
- スカラー倍は、
本記事では、 の部分空間の基底を管理するのに便利なアルゴリズムと、その正当性についてまとめています。
アルゴリズムの実装
struct XorVecSpace { // 部分空間の基底を蓄える配列 vector<int> basis; // 部分空間の生成元を追加、basisのサイズ(部分空間の次元)が大きくなったらtrueを返す bool add(int v) { int mn = minimize(v); if (mn) basis.push_back(mn); return mn != 0; } // 部分空間の元であるかを判定 bool is_element(int v) const { return minimize(v) == 0; } // 部分空間の元とvとの和の最小値を計算 int minimize(int v) const { for (int eb : basis) { v = min(v, v ^ eb); } return v; } // 部分空間の元とvとの和の最大値を計算 int maximize(int v) const { for (int eb : basis) { v = max(v, v ^ eb); } return v; } // 部分空間の次元を返す int dim() const { return basis.size(); } };
以下では、自然数の集合 が生成する の部分空間を と書きます。
- 配列
basis
(以下では と書くことにします) に現在管理している部分空間の基底が蓄えられます。 add
:部分空間の生成元として を追加し、次元が大きくなったか否かを返します。 このとき、渡した元そのものが に入るわけではないので、未加工の元からなる基底が欲しい場合は別途管理する必要があります。is_element
: であるかを判定します。minimize
:集合 の最小元を返します。maximize
:集合 の最大元を返します。dim
:部分空間の次元を返します。
アルゴリズムの正当性
まず、add
関数の正当性を示すことを考えます。add
関数でやっていることは、集合 の最小元 を求め、 ならば なので に を追加する、ということです。よって、minimize
関数の正当性を示せばよいです。
とし、 の最上位ビットを 桁目とします。minimize
関数でやっていることは、 の順に、以下で定義される操作 を に施すということです。
操作 : の 桁目が ならば に を足す。
add
関数によって蓄えられる基底 がもつ以下の性質によります。において 桁目は である。
add
関数で に が追加されたとき、 の 桁目は であることを示せばよい。minimize
関数において、操作 の直後、 の 桁目は であるが、帰納法の仮定により、以降の操作で 桁目に干渉することはないため、 においても 桁目は になる。 □さて、この性質を使うことでminimize
関数の正当性を示すことができます。minimize
関数でやりたいことは、 の順に、 に を足すor足さないの操作をすることで、 の最終的な値を最小化するということです。性質より、 の 桁目は 番目よりあとの操作で不変です。つまり、 番目の操作によって の 桁目の最終的な値を決めることができます。また、 番目の操作では の 桁目より上の桁には干渉しません。 これらを踏まえると、 の最終的な値を最小化するには、操作 のようにすればよいです。したがって、minimize
関数の正当性がわかりました。
maximize
関数の正当性もminimize
関数の正当性と同様に理解することができます。
おまけ
bitsetバージョンの実装例です。bitsetのmsbを求める関数がないのはなぜでしょうか?std::bitset::_Find_first
でlsbは求まるので、次元を求めるだけならこれを使って実装してもよいと思います。ただし、最小化、最大化などは壊れてしまいます。
template <int N> struct XorVecSpace { using bs = bitset<N>; // 部分空間の基底を蓄える配列 vector<bs> basis; // 基底のmsbをもっておく vector<size_t> msb; // 部分空間の生成元を追加、basisのサイズ(部分空間の次元)が大きくなったらtrueを返す bool add(const bs& v) { bs mn{minimize(v)}; if (mn.none()) return false; basis.emplace_back(mn); msb.emplace_back(N - 1); while (!basis.back().test(msb.back())) --msb.back(); return true; } // 部分空間の元であるかを判定 bool is_element(const bs& v) const { return minimize(v).none(); } // 部分空間の元とvとの和の最小値を計算 bs minimize(bs v) const { for (int i = 0; i < (int)basis.size(); ++i) { if (v.test(msb[i])) v ^= basis[i]; } return v; } // 部分空間の元とvとの和の最大値を計算 bs maximize(bs v) const { for (int i = 0; i < (int)basis.size(); ++i) { if (!v.test(msb[i])) v ^= basis[i]; } return v; } // 部分空間の次元を返す int dim() const { return basis.size(); } };