By _Muhammad, history, 9 months ago, ,  Comments (4)
 » 9 months ago, # | ← Rev. 2 →   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(); } }
 » 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]