- #1
rasman
- 8
- 0
Let's say I have 10 items, and I want to examine every combination of 5 items. Obviously, there are http://www.google.com/search?q=10+choose+5" possible combinations. But I want to actually enumerate them and iterate through them as efficiently as I can in a computer program. I'm wondering what the best way to do this might be. I don't know/remember much about combinatorics, and I'm hoping that this problem has been solved already.
So far, the best thing I can think of is to iterate from the smallest 10-bit number that has 5 bits set...
...to the largest 10-bit number that has 5 bits set...
...and check every value between them to see if it has exactly 5 bits set.
Can anyone think of a better way? Has this problem been solved already? How can I get the next highest integer with the same number of bits set?
Thanks for any insight that you can provide.
So far, the best thing I can think of is to iterate from the smallest 10-bit number that has 5 bits set...
Code:
int min = (1 << 5) - 1; // 0000011111 = 31
...to the largest 10-bit number that has 5 bits set...
Code:
int max = min << 5; // 1111100000 = 992
...and check every value between them to see if it has exactly 5 bits set.
Can anyone think of a better way? Has this problem been solved already? How can I get the next highest integer with the same number of bits set?
Thanks for any insight that you can provide.
Last edited by a moderator: