Subset xor problem (need help)

Revision en2, by skavurskaa, 2016-04-01 18:17:22

I am solving a problem where a set of N K-bit integers is given (N <= 10^4, K <= 50). I am allowed to do a single operation: choose two numbers A,B from the set and insert A xor B into the set.

The problem asks if it is possible, for the given set, to generate all numbers from 0 to 2K - 1 using only this operation, as many times as i want.

I read that this can be solved using Gaussian Elimination, but i don't know how to do it. Can any one help me with this problem? Thx in advance :)

EDIT : I solved the problem. Thanks to Enchom for the awesome algorithm! To the ones interested, here are the original problem statement and my solution:


  Rev. Lang. By When Δ Comment
en2 English skavurskaa 2016-04-01 18:17:22 275 problem solved
en1 English skavurskaa 2016-04-01 02:39:17 525 Initial revision (published)