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?
risposta
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()
C'è un modo migliore quando sappiamo che il numero massimo di bit di qualsiasi numero nell'array può arrivare fino a 10 solo? – user3522401
Può esserci una soluzione ricorsiva proprio come il problema della somma parziale? – user3522401
Questo codice indica se esiste una soluzione e, in caso affermativo, quanti? –
solo un'idea: Ordina l'array, in questo modo si controlla le somme fino a numeri inferiori a 7. – mounaim
"Efficient" ...? Tempo, memoria, complessità teorica? – deviantfan
@mounaim Stai dicendo che i numeri> 7 non possono far parte della soluzione? Sbagliato. – deviantfan