2014-12-06 17 views
5

Ho un array intero positivo- {1,5,8,2,10} e un valore dato 7. Ho bisogno di trovare se esiste un sottoinsieme dell'array tale che lo XOR dei suoi elementi sia il valore 7 In questo caso il sottoinsieme è {5,2} perché 5 xor 2 è 7. Una soluzione ingenua è quella di trovare tutti i sottoinsiemi e verificare se esiste una soluzione. Voglio un algoritmo migliore rispetto all'ingenuo. NOTA: -Ho solo bisogno di trovare se esiste una soluzione o no.Non ho bisogno di trovare il sottoinsieme.Algoritmo efficiente per scoprire se esiste un sottoinsieme di un array intero, l'xor di tutti i suoi elementi è un valore dato?

+0

solo un'idea: Ordina l'array, in questo modo si controlla le somme fino a numeri inferiori a 7. – mounaim

+3

"Efficient" ...? Tempo, memoria, complessità teorica? – deviantfan

+1

@mounaim Stai dicendo che i numeri> 7 non possono far parte della soluzione? Sbagliato. – deviantfan

risposta

5

Questo si riduce alla soluzione di un sistema di equazioni lineari sul campo finito con due elementi (GF (2)). Qui XOR bit a bit equivale all'aggiunta di due vettori. Gli ingressi di esempio corrispondono a vettori come questi.

1: 0001 
5: 0101 
8: 1000 
2: 0010 
10: 1010 
7: 0111 

Il sistema si presenta così.

[0 0 1 0 1] [a] [0] 
[0 1 0 0 0] [b] [1] 
[0 0 0 1 1] [c] = [1] 
[1 1 0 0 0] [d] [1] 
       [e] 

Il seguente codice Python usa Gaussian elimination ed è implementato utilizzando operazioni bit per bit. Per numeri interi a larghezza fissa, viene eseguito in tempo lineare. Perdonami, non riesaminando l'eliminazione gaussiana quando ci sono già un milione di trattamenti migliori su Internet.

#!/usr/bin/env python3 
def least_bit_set(x): 
    return x & (-x) 


def delete_zeros_from(values, start): 
    i = start 
    for j in range(start, len(values)): 
     if values[j] != 0: 
      values[i] = values[j] 
      i += 1 
    del values[i:] 


def eliminate(values): 
    values = list(values) 
    i = 0 
    while True: 
     delete_zeros_from(values, i) 
     if i >= len(values): 
      return values 
     j = i 
     for k in range(i + 1, len(values)): 
      if least_bit_set(values[k]) < least_bit_set(values[j]): 
       j = k 
     values[i], values[j] = (values[j], values[i]) 
     for k in range(i + 1, len(values)): 
      if least_bit_set(values[k]) == least_bit_set(values[i]): 
       values[k] ^= values[i] 
     i += 1 


def in_span(x, eliminated_values): 
    for y in eliminated_values: 
     if least_bit_set(y) & x != 0: 
      x ^= y 
    return x == 0 


def main(): 
    values = [1, 5, 8, 2, 10] 
    eliminated_values = eliminate(values) 
    print(eliminated_values) 
    x = int(input()) 
    print(in_span(x, eliminated_values)) 


if __name__ == '__main__': 
    main() 
+0

C'è un modo migliore quando sappiamo che il numero massimo di bit di qualsiasi numero nell'array può arrivare fino a 10 solo? – user3522401

+0

Può esserci una soluzione ricorsiva proprio come il problema della somma parziale? – user3522401

+0

Questo codice indica se esiste una soluzione e, in caso affermativo, quanti? –