I haven't read the algorithm code, but I think you can do the following? For n items, pick a random k https://code.activestate.com/recipes/126037-getting-nth-perm...
Algorithm No One Knows About (2016)
11–20 of 200 posts
Re: Algorithm No One Knows About (2016)
#12>The misleading part in using the language of cards is that you don’t often consider a deck of size 2^64. What’s nice about the card formulation though is that it conveys how simple the problem statement really is. This is a fundamental problem that was open for a long time. Nobody knew how to deal cards. >The first obstacle that makes the “dealing” (without replacement) hard is that the “draw” method doesn’t work. I…
A use case may be shuffling the entire list, if I'm not mistaken?
Re: Algorithm No One Knows About (2016)
#13While reading, I was thinking about LFSR [0] with suitable properties and period. Not strictly random, although LFSRs are commonly used for generating "random" numbers.
[0]: https://en.wikipedia.org/wiki/Linear-feedback_shift_register
Re: Algorithm No One Knows About (2016)
#14>The misleading part in using the language of cards is that you don’t often consider a deck of size 2^64. What’s nice about the card formulation though is that it conveys how simple the problem statement really is. This is a fundamental problem that was open for a long time. Nobody knew how to deal cards. >The first obstacle that makes the “dealing” (without replacement) hard is that the “draw” method doesn’t work. I…
> How is this true? If you're drawing from a deck of 2^64 cards then unless you're drawing almost all of them there's not going to be any problem with rejection. Even if you're drawing 2^63 card you're going to be rejecting only half of your draws, so the average slowdown is going a factor of 2. 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 rejec…
Birthday problem says that once you've gone through ~2^8 cards you've got a ~50% of having had to reject at least once. It takes 2^63 until you have a 50% chance of rejecting on each draw.
Re: Algorithm No One Knows About (2016)
#15Why is hashmap not good enough for unique ID generation? const tweetIDs = {}; while(TWEET_COUNT){ const rnd = Math.random() * MAX_TWEET_ID; if(!tweetIDs[rnd]){ tweetIDs[rnd] = true; TWEET_COUNT--; } }
>The main one is that eventually you’re ignoring too many cards and the algorithm doesn’t finish on time (this is the coupon collector’s problem).
This will take longer time at each iteration and when both MAX_TWEET_ID and and TWEET_COUNT is large and close to (or equal to) each other it may take very long to complete.
Re: Algorithm No One Knows About (2016)
#16"(Stated more formally: given non-negative integers k and n with k "...it’s also possible to use the language of cards: deal k cards from a deck of size n, without replacement. So a poker hand like A2345 of clubs is valid for k=5 and n=52, but a hand containing AAAAA of clubs is not."
These seem to be fairly straight forward problems to solve- can anybody ELI5 why the Vitter algorithm is necessary?
Re: Algorithm No One Knows About (2016)
#17Earlier quoted context omitted.
That gets pretty slow and memory intensive once you sample a large amount of the total doesn’t it?
It was not a requirement :) However it won't get slow, it's O(1) to lookup if a key exists.
It will get slow towards the end once each loop iteration has a very low chance of being productive (only happens when you're choosing all or almost all elements). You can fix that, though there's potential tradeoffs.
Re: Algorithm No One Knows About (2016)
#18Earlier quoted context omitted.
That gets pretty slow and memory intensive once you sample a large amount of the total doesn’t it?
It was not a requirement :) However it won't get slow, it's O(1) to lookup if a key exists.
> (Stated more formally: given non-negative integers k and n with k As k approaches n the expected number of draws needed to get k unique values increases faster than O(k).
Re: Algorithm No One Knows About (2016)
#19Earlier quoted context omitted.
> How is this true? If you're drawing from a deck of 2^64 cards then unless you're drawing almost all of them there's not going to be any problem with rejection. Even if you're drawing 2^63 card you're going to be rejecting only half of your draws, so the average slowdown is going a factor of 2. 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 rejec…
Birthday problem says that once you've gone through ~2^8 cards you've got a ~50% of having had to reject at least once. It takes 2^63 until you have a 50% chance of rejecting on each draw.
Ah, right. I wasn't thinking properly. Thanks for the explanation.
Re: Algorithm No One Knows About (2016)
#20Can't you use https://en.wikipedia.org/wiki/Lehmer_random_number_generator for this? I thought that was a common method of generating a random sequence without repetition. True, the result is not very random, but in most applications it doesn't make much of a difference.
[deleted]