Vamos a la "longitud" de un número será el número de dígitos necesarios para escribir en binario, con exclusión de cualquier ceros a la izquierda. De forma equivalente, la longitud de un número es la posición de los líderes de la $1$ poco en su representación binaria.
Claramente, si todos los números introducidos tenía una longitud diferente, el problema tendría una solución trivial: sólo iterar a través de la entrada de números en orden decreciente por la longitud, la elección de cada número, si y sólo si el cifrado xor con la máxima hasta el momento aumenta la máxima, es decir, si y sólo si su bit inicial no se establece en el máximo actual.
Dado que este es un algoritmo pregunta, permítanme dar algunos pseudo-código para ilustrar el algoritmo que acabo de describir:
# Find maximum XOR of input, assuming that all input numbers have
# different length:
let max = 0
for each number n in input (sorted in descending order by length):
if max < (max XOR n): let max = (max XOR n)
(Para ver por qué este algoritmo funciona, primero observar que cada uno de los bits en un número binario se "vale" más que todo la parte inferior de bits combinado, por lo que claramente quiere trabajar de arriba hacia abajo, primero la optimización de la más alta bits, no importa lo que esto hace a la parte inferior de bits.
Ahora, supongamos que ya hemos considerado todos los número de entrada más de $k$ bits, y determina el máximo valor de los bits más altos de $k$ puede tener en su XOR, y que ahora estamos considerando si XOR $k$-el número de bits — que, por supuesto de arriba, es la única $k$-el número de bits de la entrada — en el máximo o no. No podemos cambiar los bits por encima de la $k$-ésimo bit por hacerlo, pero les puede asegurarse siempre de que la $k$-ésimo bit en el resultado se establece, mediante el cifrado xor el actual número de entrada en el resultado si y sólo si el $k$-ésimo bit del resultado hasta la fecha aún no está establecida. Además, asegurar que el $k$-ésimo bit está establecido es claramente más importante que cualquier cosa que pueda suceder a la parte inferior de bits como un efecto secundario, por lo que podemos ignorar los bits por ahora.)
La parte difícil es cuando la entrada puede contener varios números con la misma longitud, desde luego, no es obvio cuál de ellos debemos elegir incluir en la operación XOR. Lo que nos gustaría hacer es reducir la lista de entrada en una forma equivalente que no contenga más de un número de la misma longitud.
Muy bien, esto es exactamente lo que la eliminación Gaussiana : transforma una lista de vectores en otra lista de vectores que tienen estrictamente decreciente de longitud, como se definió anteriormente (es decir, en una lista que está en forma escalonada), pero que todavía se extiende por el mismo subespacio lineal.
La razón de esta álgebra lineal algoritmo que es relevante aquí es que los números binarios satisfacer los axiomas de un espacio vectorial sobre el campo finito de dos elementos, un.k.una. GF(2), con los números vistos como vectores de bits, y con XOR como el vector de la operación de adición. (También tenemos una multiplicación escalar de operación para satisfacer los axiomas, pero eso es trivial, ya que los únicos escalares en GF(2)$1$$0$.)
El lineal subespacio generado por un conjunto de vectores de bits (es decir, los números binarios) sobre GF(2) es simplemente el conjunto de vectores que se pueden obtener mediante el cifrado xor un subconjunto de ellos. Por lo tanto, si podemos usar eliminación Gaussiana para convertir nuestra lista de entrada en uno de otro, que se extiende por el mismo subespacio, podemos resolver el problema de usar esta lista de otros y saber que se le da la misma solución para el problema original.
Por lo tanto, necesitamos implementar eliminación Gaussiana sobre GF(2). Afortunadamente, este resulta ser muy simple (de hecho, mucho más sencillo que hacerlo para el común de los vectores de números reales):
Encontrar la longitud máxima $k$ de los (restantes) entradas, y al menos una entrada teniendo esa longitud. Poner esta entrada en un lado.
XOR todas las otras entradas de la longitud de la $k$ con el conjunto de entrada a un lado en el paso 1: su longitud será ahora menos de $k$.
Repita desde el paso 1, hasta que el resto de los insumos de la longitud de $0$ (y por lo tanto puede ser descartado).
Las entradas de lado durante las sucesivas iteraciones del paso 1 anterior se forma la nueva entrada de la lista. (Muy bien, ya que en orden decreciente según su longitud.)
Una utilidad de optimización es separar las entradas en un número de "cubos" (es decir, de longitud variable listas) por su duración: esta hace que la búsqueda de la máxima longitud, y todos los insumos que la longitud de una forma muy fácil y eficiente.
He aquí algunos pseudo-código de nuevo:
# Preliminary phase: split numbers into buckets by length
for each number x in input:
let k = length of x
if k > 0: add x to bucket k
# Gaussian elimination:
for each bucket (in decreasing order by k):
if this bucket is empty: skip rest of loop
let x = arbitrary (e.g. first) number in this bucket
remove x from this bucket
add x to modified input list
for each remaining number y in this bucket:
remove y from this bucket
let z = y XOR x
let k = length of z
if k > 0: add z to bucket k
A continuación, sólo hay que aplicar la máxima encontrar el algoritmo dado anteriormente a la modificación de la lista de entrada.
(Ps. También es posible encontrar el subconjunto de los números introducidos dando el máximo XOR utilizando este algoritmo: para cada modifica el número de entrada, solo se necesita alguna manera de seguir la pista de los cuales original de entrada de números fue XORed. Este es básicamente el mismo algoritmo que el uso de eliminación Gaussiana para encontrar una matriz inversa, sólo adaptadas a vectores de bits.)
