2^63 is half of 2^64. For the last draw, each time you try to pick an unused, what's the odds it was taken already? (approx 1/2) You won't have to try too many times. The draws before the last are strictly better, so overall you should be fine.
2^63 is half of 2^64. For the last draw, each time you try to pick an unused, what's the odds it was taken already? (approx 1/2) You won't have to try too many times. The draws before the last are strictly better, so overall you should be fine.
One algorithm that I haven't yet seen mentioned in this discussion is: shuffle the array of choices, pick the first k.
If you're clever about it, this has some nice properties: you can stop shuffling after the first k, and if you want you can start reporting results immediately. (You'd want to use something like Fisher-Yates to shuffle for these properties)
This also wouldn't use much extra space, and doesn't require special handling for small or large k.
Biggest downside is it will change the order of the original set. And it's only worth doing if you already have an array full of the items to choose, most likely.