By _Muhammad, history, 14 months ago, ,

After applying Gaussian algorithm on a array how could I restore those numbers of which XOR is maximum?

Let a[3] = {11, 5, 9} If I apply Gaussian algorithm we will find maximum xor is 14.And used numbers are 11, 5.How to restore this 11, 5?

• +13

 » 14 months ago, # | ← Rev. 2 →   0 if you have additional time (where c is the max value) it is easy to restore. Here is a slow implementation, which can be improved to if you replace the bitset and just store by wich indices the value is composed (there are always atmost bits set). bitset calc(const vector& in) { vector val = in; bitset res; vector> set(in.size()); for (ll i = 0; i < n; i++) set[i][i] = true; ll c = 0; while (true) { ll m = 0; for (ll i = 0; i < n; i++) { if (val[m] < val[i]) m = i; } if (val[m] == 0) return res; if ((c ^ val[m]) > c) { c ^= val[m]; res ^= set[m]; } for (ll i = 0; i < n; i++) { if (i != m && (val[i] ^ val[m]) < val[i]) { val[i] ^= val[m]; set[i] ^= set[m]; } } val[m] = 0; set[m].reset(); } } 
•  » » 14 months ago, # ^ | ← Rev. 2 →   0 Thanks man. I got. :)
 » 14 months ago, # |   +3 I did a python 2 implementation to show one way of doing it, in , where m is the number of linear independent binary vectors in A. Note that so it runs really quick, also note that nothing in my implementation is python specific I just really like how pseudo code like python is. The essential stuff lies in the two functions, the rest just shows how to use the functions. A = [11, 5, 9] def linear_independent_basis(A): basis_indices = [] while any(A): i = max(range(len(A)),key = lambda i: A[i]) basis_indices.append(i) Amax = A[i] A = [min(a^Amax,a) for a in A] return basis_indices def orthogonalize(B): m = len(B) Bprime = B[:] # store bitmasks to remember how to recreate Bprime from B bitmasks = [2**i for i in range(m)] for i in range(m): for j in range(m): if i!=j and Bprime[i]^Bprime[j]
•  » » 14 months ago, # ^ | ← Rev. 2 →   0 I didn't get anything. I have a little knowledge of python. But thanks.You tried to help me.