It it though? I'm a but shoddy on my mathematics, but I'd wager from the birthday problem that you'd probably have to reject much more than half of the 'cards', and as you get to the end, you'd have to redraw several times for each card.
It it though? I'm a but shoddy on my mathematics, but I'd wager from the birthday problem that you'd probably have to reject much more than half of the 'cards', and as you get to the end, you'd have to redraw several times for each card.
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.