Hi, I want to write an algorithm, in which it needs to find all subset of k elements from the set {1,2,...,n} elements, for k=1,...,p (p is defined by user),
I have no idea to write code which efficient in speed and memory,
Can anybody help me?
Just loop a large enough bit size integer from 1 to 2^n inclusive exclusive. If the parity of the integer is less than or equal p then the integer represents a valid subset of size k<=p. Item i is in the subset if bit i of the integer is 1.
Calculating the parity can be a bit slow. If this is an issue then precalculate a lookup table for the parity of an 8 bit number and then split the integer into 8 bit numbers.
With carful thought, and small p, you can optimize to skip a lot of integers.
As this is a fairly obvious homework assignment, I'm not so sure the OP has received the help he needs. I would also warn him against turning in anything like JLBorges's code. Even though he made it really simple it is still beyond anything the teacher will expect you to personally produce.
Thanks for your consideration, I need subset of k elements of {1,2,..,n} for my algorithm in "Network Theory", This is only a partial task of the algorithm and in best scenario k=100 and n=1000. that the best way mentioned by JLBorges using Gray codes, seems not work. how can I generate a subset of k elements of {1,2,..,n} randomly?