3 ms·
That seems correct. On top of that, if you ever need to choose more than half, you choose n-k first then reverse the set. Could it be that the distribution cond
by mihaifm 7y ago
That seems correct. On top of that, if you ever need to choose more than half, you choose n-k first then reverse the set. Could it be that the distribution condition is not satisfied? Although I don’t see how. The article could’ve explained the problem better (I mean it keeps reffering to “draw without replacement” - what does that even mean).
- kadoban 7y agoThe "choose n-k" trick is quite nice. It has one big downside though, which is that you can't start reporting any results until you're totally done. 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.
- SamBam 7y agoI think the article discusses the fact that shuffling the entire initial set takes up way too much memory.