ゼロまでの整数の配列の最大部分集合をどのように見つけるか

Question

xorsを0にする[0,1,4,5,6,8]という配列の最大部分集合を明確にするために、[0 、1,4,5]は0^1^4^5 = 0（ここで、^はxorであるから）である。私はこれが指数関数的な時間でブルートフォースで行うことができることを知っていますが、私は下界が何であるか、そしてそのアルゴリズムをどのようなアルゴリズムで解いているのか知りたいと思います。

私はRationalシーブアルゴリズムを実装しています。 wikipedia articleを超えて、アルゴリズム上のリソースはかなり不足しています。合理的なふるいを完了するためには、配列のグループのサブセットを見つけようとします。対応する要素を追加するとき、結果の配列は偶数だけを持ちます。例：

[2,3,4,5] + [4,3,4,3] = [6,6,8,8]これは有効な解決策です。より大きなセット。

このウィキペディアの記事によれば、これは線形代数を使って解くことができますが、それを解決するのに十分な線形代数はわかりません。

アルゴリズムの目的上、空のサブセットは有用ではありません。

私は、配列が0と1だけを持つことができ、配列を単一の数値にすることで、合計が1つの演算子で計算できるようにすることで問題を簡素化しました。

Answer 1

はい、線形最適化の問題として定式化できます。整数kビットであり、それらのnが存在すると仮定すると、次の列は整数を表すk * nマトリックスA、としてそれらを表すことができ、そしてカラムnの行r整数iのr番目のビットです。

整数の選択と消去は、A * xと表すことができます。ここで、xは、選択された整数の位置に1秒を持つサイズnのベクトルです。これはGF（2）を超えなければならないので、乗算が標準的であり、加算はXORである。だからAx = 0の対象となるのはmaximize(|x|)です。