任意の排他的論理和の組み合わせから生成できない1つの数値を取得する効率的な方法

Question

[0 .. 2 ]の範囲内に1つ以上のXORの構成では生成できない数値がある場合到達不可能な番号の少なくとも1つを出力するか、または情報で終了する、到達不能な番号がないという効率的な方法がありますか？ この問題に名前がありますか？それは別の問題に似ているのですか、それとも解決する方法がありますか？

Answer 1

各数値は、Z/2のベクトル空間（Z/2）^ 64でベクトルとして扱うことができます。基本的には与えられたベクトルが全空間にまたがっているかどうかを知りたければ、スパンされていないベクトルを生成します（スパンには常にゼロベクトルが含まれていますが、実際には1つ以上の場合は特別な場合があります） 。これは、ガウス消去を使用して実行できます。

この特定のベクトル空間では、ガウス消去は非常に簡単です。基になる空のセットから始めます。それ以上番号がなくなるまで、次の操作を行います。 （1）ゼロの数字のすべてを取り除く。 （2）残りの数字の下位ビットセット（xの最下位ビットはx & ~(x - 1)）をスキャンし、最下位ビットがセットされているものを選択します。 （3）それを基礎にしてください。 （4）それを新しい基底要素と排他的論理和することによって、その同じビットで他のすべての数を更新する。残りの数にはこのビットまたは下位ビットが設定されていないので、64回の反復後に終了します。

最後に、64個の要素がある場合、部分空間はすべてです。さもなければ、私たちは64回以下の反復を行い、ちょっとスキップしました。このビットだけの数はスパンしません。

特殊ケースの場合：ゼロは、数値を捨てない（入力ベクトルが独立している）場合に限り、オプションです。 4ビット数0110と

スタート、0011、1001、1010、それはものはビットセットがあるため、0011を選択してください経由

---

例。基礎は今{0011}です。他のベクトルは、{0110,1010,1010}である。最初の1010 = 1001 XOR 0011.

2つのビットが設定されているため、0110を選択してください。基底は今{0011,0110}です。他のベクトルは{1100,1100}です。

を選択します。基準は{0011、0110、1100}になりました。他のベクトルは{0000}です。

0000を捨てます。上位ビットをスキップしたので、1000はスパンに含まれていません。

Answer 2

ラップミュージックは、ベクトル空間でベースを見つけると考えることができます。しかし、実際にそれを完全に解く必要はありません。そうすることができるかどうかを調べるだけで、そうでない場合は、提供されたセットに関して記述できない値（バイナリベクトル）を与えます。 。

これは、入力セットのサイズに関してO（n^2）で行うことができます。これは、O（n^3）,http://en.wikipedia.org/wiki/Gaussian_eliminationであるガウス消去と比較する必要があります。

64ビットはまったく問題ありません。例のPythonコードでは、0〜2の1000のランダム値を持つ1000ビットが1000〜1に設定されます。1000-1には約1秒かかります。4ビット版:)

original  triangular 
1110 14   1110 14 
1011 11   111 7 
    111 7   11 3 
    11 3   1 1 
    1 1   0 0 

ソリューションの作品のために（：それは私たちのような三角形のフォーム上のすべてのビットの行列を書き換えることができるかどうかを知るには十分だガウス消去を実行

代わりの同じような最上位ビットを持つ最初のすべての元の値は、リストのリストにまとめられています。例：

[[14,11],[7],[3],[1],[]] 

最後の空のエントリは、元のリストにゼロがないことを表します。さて、最初のエントリから値を取得してのみ、その番号を含むリストでそのエントリを置き換えます

[[14],[7],[3],[1],[]] 

をし、その後、ベクターで適切な場所にすべて削除されたエントリで保持数のXORを格納します。我々の場合のために我々は14^11 = 5これがあります。

[[14],[7,5],[3],[1],[]] 

トリックは、我々は他のすべての値、同じ最上位ビットとの値だけをスキャンして更新する必要がないということです。

同じように項目7,5を処理します。 3,2葉今

[[14],[7],[3,2],[1],[]] 

[3]と1を追加します：リストに= 2 7^5を追加し、7をキープ

[[14],[7],[3],[1,1],[]] 

と1,1-葉[1]と0を追加ノーセットビットに値を可能に最後のエントリに：最後に、ベクターは、（この例のように）各ベクタエントリに少なくとも一つの番号が含まれている場合

[[14],[7],[3],[1],[0]] 

塩基は完了し、任意の数収まります。

はここで完全なコードです：

# return leading bit index ir -1 for 0. 
# example 1 -> 0 
# example 9 -> 3 
def leadbit(v): 
    # there are other ways, yes... 
    return len(bin(v))-3 if v else -1 

def examinebits(baselist,nbitbuckets): 
    # index 1 is least significant bit. 
    # index 0 represent the value 0  
    bitbuckets=[[] for x in range(nbitbuckets+1)] 
    for j in baselist: 
     bitbuckets[leadbit(j)+1].append(j) 
    for i in reversed(range(len(bitbuckets))): 
     if bitbuckets[i]: 
      # leave just the first value of all in bucket i 
      bitbuckets[i],newb=[bitbuckets[i][0]],bitbuckets[i][1:] 
      # distribute the subleading values into their buckets 
      for ni in newb: 
       q=bitbuckets[i][0]^ni 
       lb=leadbit(q)+1 
       if lb: 
        bitbuckets[lb].append(q) 
       else: 
        bitbuckets[0]=[0] 
     else: 
      v=2**(i-1) if i else 0 
      print "bit missing: %d. Impossible value: %s == %d"%(i-1,bin(v),v) 
      return (bitbuckets,[i])  
    return (bitbuckets,[]) 

使用例：（8ビット）

import random 
nbits=8 
basesize=8 
topval=int(2**nbits) 
# random set of values to try: 
basel=[random.randint(0,topval-1) for dummy in range(basesize)] 
bl,ii=examinebits(basel,nbits) 

blが、それは不可能だった時点まで、今の値の三角形のリストである（中その場合）。失われたビット（ある場合）はii [0]にあります。値の次しようとしたセットについて

：[242, 242, 199, 197, 177, 177, 133, 36]三角形のバージョンは次のとおりです。

base value: 10110001 177 
base value: 1110110 118 
base value: 100100 36 
base value: 10000 16 
first missing bit: 3 val: 8 
(the below values where not completely processed) 
base value:  10 2 
base value:  1 1 
base value:  0 0 

上記のリストは、このように印刷された：

for i in range(len(bl)): 
    bb=bl[len(bl)-i-1] 
    if ii and len(bl)-ii[0] == i: 
     print "example missing bit:" ,(ii[0]-1), "val:", 2**(ii[0]-1) 
     print "(the below values where not completely processed)" 
    if len(bb): 
     b=bb[0] 
     print ("base value: %"+str(nbits)+"s") %(bin(b)[2:]), b