Metodo efficiente per ottenere un numero, che non può essere generato da alcuna combinazione XORing

Question

Se c'è un numero nell'intervallo [0 .. 2 ] che non può essere generato da alcuna composizione XOR di uno o più numeri da un dato insieme, c'è un metodo efficiente che stampa almeno uno dei numeri irraggiungibili, o termina con le informazioni, che non ci sono numeri irraggiungibili? Questo problema ha un nome? È simile ad un altro problema o hai qualche idea, come risolverlo?

Answer 1

Ogni numero può essere considerato come un vettore nello spazio vettoriale (Z/2)^64 su Z/2. Fondamentalmente vuoi sapere se i vettori dati occupano tutto lo spazio, e se no, per produrne uno non spanning (eccetto che lo span include sempre il vettore zero - dovrai fare caso speciale se vuoi veramente uno o più) . Questo può essere ottenuto tramite l'eliminazione gaussiana.

Su questo particolare spazio vettoriale, l'eliminazione gaussiana è piuttosto semplice. Inizia con un set vuoto per la base. Fai quanto segue fino a quando non ci saranno più numeri. (1) Butta via tutti i numeri che sono zero. (2) Scansionare il set di bit più basso dei numeri rimanenti (il bit più basso per x è x & ~(x - 1)) e scegline uno con il bit di ordine più basso impostato. (3) Mettilo nella base. (4) Aggiorna tutti gli altri numeri con lo stesso bit impostato da XOR con il nuovo elemento base. Nessun numero rimanente ha questo bit o alcun bit di ordine inferiore impostato, quindi terminiamo dopo 64 iterazioni.

Alla fine, se ci sono 64 elementi, il sottospazio è tutto. Altrimenti, siamo andati meno di 64 iterazioni e abbiamo saltato un po ': il numero con solo questo bit non è spanning.

A zero caso speciale: zero è un'opzione se e solo se non si elimina mai un numero (vale a dire, i vettori di input sono indipendenti).

---

Esempio over numeri a 4 bit

iniziare con 0110, 0011, 1001, 1010. Scegli 0011 perché ha i bit impostato. La base è ora {0011}. Altri vettori sono {0110, 1010, 1010}; si noti che il primo 1010 = 1001 XOR 0011.

Scegliere 0110 perché ha il bit di due bit impostato. La base è ora {0011, 0110}. Altri vettori sono {1100, 1100}.

Scegliere 1100. La base ora è {0011, 0110, 1100}. Altri vettori sono {0000}.

Gettare via 0000. Abbiamo finito. Abbiamo saltato il bit di ordine elevato, quindi 1000 non è compreso nell'intervallo.

Answer 2

As rap music indica che si può pensare al problema come trovare una base in uno spazio vettoriale. Tuttavia, non è necessario risolverlo completamente, solo per scoprire se è possibile farlo o no, e se no: dare un valore di esempio (cioè un vettore binario) che non può essere descritto in termini di set fornito .

Questo può essere fatto in O (n^2) in termini di dimensioni del set di input. Questo dovrebbe essere confrontato con l'eliminazione di Gauss che è O (n^3), http://en.wikipedia.org/wiki/Gaussian_elimination.

64 bit non sono affatto un problema. Con il codice Python di esempio sotto 1000 bit con un set con 1000 valori casuali da 0 a 2^1000-1 impiega circa un secondo.

Invece di eseguire Gauss eliminazione è sufficiente per scoprire se è possibile riscrivere la matrice di tutti i bit di forma triangolare, come: (per la versione a 4 bit :)

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

Le opere soluzione in questo modo: per prima cosa tutti i valori originali con lo stesso bit più significativo vengono messi insieme in un elenco di elenchi. Per il nostro esempio:

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

L'ultima voce vuota indica che non ci sono stati zeri nell'elenco originale. Ora, prendete un valore dalla prima voce e sostituire la voce con una lista contenente solo quel numero:

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

e quindi memorizzare lo XOR del numero tenuto con tutte le voci rimossi al posto giusto nel vettore. Per il nostro caso abbiamo 14^11 = 5 così:

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

Il trucco è che non abbiamo bisogno di eseguire la scansione e aggiornare tutti gli altri valori, solo i valori con lo stesso bit più significativo.

Ora elaborare l'elemento 7,5 nello stesso modo. Mantenere 7, aggiungere 7^5 = 2 alla lista:

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

Ora 3,2 foglie [3] e aggiunge 1:

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

E 1,1 foglie [1] e aggiunge 0 all'ultima voce consentendo valori senza bit impostato:

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

Se alla fine il vettore contiene almeno un numero ad ogni entrata vettore (come nel nostro esempio) la base è completa e qualsiasi numero adatto.

Ecco il codice completo:

# 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,[]) 

uso Esempio: (8 bit)

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 è ora l'elenco triangolare di valori, fino al punto in cui non era possibile (in questo caso). Il bit mancante (se presente) si trova in ii [0].

Per la seguente serie di valori provato: [242, 242, 199, 197, 177, 177, 133, 36] la versione triangolare è:

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 

questo elenco sono state stampate in questo modo:

numeri

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