Método eficiente para obtener un número, que no se puede generar desde ninguna combinación XORing

Question

Si hay algún número en el rango [0 .. 2 ] que no puede ser generado por ninguna composición XOR de uno o más números de un conjunto dado, ¿hay algún método eficiente que imprima al menos uno de los números inalcanzables o termine con la información de que no hay números inalcanzables? ¿Este problema tiene un nombre? ¿Es similar a otro problema o tienes alguna idea de cómo resolverlo?

Answer 1

Cada número se puede tratar como un vector en el espacio vectorial (Z/2)^64 sobre Z/2. Básicamente, desea saber si los vectores proporcionados abarcan todo el espacio, y si no, para producir uno no abarcado (excepto que el lapso siempre incluye el vector cero - tendrá que tener un caso especial si realmente quiere uno o más) . Esto se puede lograr a través de la eliminación gaussiana.

En este espacio vectorial particular, la eliminación de Gauss es bastante simple. Comience con un conjunto vacío para la base. Haz lo siguiente hasta que no haya más números. (1) Deseche todos los números que son cero. (2) Escanee el conjunto de bits más bajo de los números restantes (el bit más bajo para x es x & ~(x - 1)) y elija uno con el conjunto de bits de orden más bajo. (3) Ponlo en la base. (4) Actualice todos los otros números con ese mismo bit establecido por XORing con el nuevo elemento de base. Ningún número restante tiene este bit o ningún bit de orden inferior establecido, por lo que finalizamos después de 64 iteraciones.

Al final, si hay 64 elementos, entonces el subespacio lo es todo. De lo contrario, recorrimos menos de 64 iteraciones y saltamos un poco: el número con solo este bit no se amplía.

Para el caso especial cero: cero es una opción si y solo si nunca tiramos un número (es decir, los vectores de entrada son independientes).

---

ejemplo más de los números de 4 bits

Start con 0110, 0011, 1001, 1010, 0011 Elija porque tiene el conjunto de bit queridos. La base ahora es {0011}. Otros vectores son {0110, 1010, 1010}; tenga en cuenta que el primer 1010 = 1001 XOR 0011.

Elija 0110 porque tiene los dos bits establecidos. La base ahora es {0011, 0110}. Otros vectores son {1100, 1100}.

Elija 1100. La base ahora es {0011, 0110, 1100}. Otros vectores son {0000}.

Tirar 0000. Hemos terminado. Nos saltamos el bit de orden alto, por lo que 1000 no está en el lapso.

Answer 2

Como rap music señala que puede pensar en el problema como encontrar una base en un espacio vectorial. Sin embargo, no es necesario resolverlo completamente, solo para ver si es posible hacerlo o no, y si no: dar un valor de ejemplo (que es un vector binario) que no se puede describir en términos del conjunto suministrado .

Esto se puede hacer en O (n^2) en términos del tamaño del conjunto de entrada. Esto se debe comparar con eliminación de Gauss que es O (n^3), http://en.wikipedia.org/wiki/Gaussian_elimination.

64 bits no son un problema en absoluto. Con el ejemplo de código python por debajo de 1000 bits con un conjunto con 1000 valores aleatorios de 0 a 2^1000-1, toma alrededor de un segundo.

En lugar de realizar Gauss eliminación es suficiente para averiguar si podemos volver a escribir la matriz de todos los bits en forma triangular, tales como: (para la versión de 4 bits :)

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

funciona la solución así: Primero todos los valores originales con el mismo bit más significativo son lugares juntos en una lista de listas. Para nuestro ejemplo:

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

La última entrada vacía indica que no hubo ceros en la lista original. Ahora, toma un valor desde la primera entrada y reemplazar esa entrada con una lista que contiene sólo ese número:

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

y luego almacenar el XOR del número guardado con todas las entradas eliminadas en el lugar correcto en el vector. Para nuestro caso tenemos 14^11 = 5, de forma:

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

El truco es que no necesitamos para escanear y actualizar todos los demás valores, sólo los valores con el mismo bit más significativo.

Ahora procese el elemento 7,5 de la misma manera. Mantenga 7, añadir 7^5 = 2 a la lista:

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

Ahora 3,2 hojas [3] y agrega 1:

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

y 1,1 hojas [1] y añade 0 a la última entrada que permite valores con ningún bit de conjunto:

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

Si al final el vector contiene al menos un número en cada vector de entrada (como en nuestro ejemplo) la base es completa y cualquier número encaja.

Aquí está el código 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,[]) 

Ejemplo uso: (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 es ahora la lista triangular de valores, hasta el punto en que no fue posible (en Ese caso). El bit faltante (si lo hay) se encuentra en ii [0].

Para el siguiente conjunto tratado de valores: [242, 242, 199, 197, 177, 177, 133, 36] la versión triangular es:

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 

La lista anterior se imprimieron como esto:

números

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