4 ms·
Generating random permutations is quite a different problem from creating random numbers. The standard algo for random permutations is the Fisher-Yates Shuffle.
by FabHK 6y ago
Generating random permutations is quite a different problem from creating random numbers. The standard algo for random permutations is the Fisher-Yates Shuffle.
https://en.wikipedia.org/wiki/Fisher–Yates_shuffle https://en.wikipedia.org/wiki/Fisher–Yates_shuffle
ETA: As you don't want to store the permutation, you might want to pick a number randomly from 1 to n!, and then generate the permutation on the fly up to the desired element, using the techniques outlined here:
https://stackoverflow.com/questions/29236556/how-can-i-calculate-n-th-permutation-or-tell-the-lexicographic-order-of-a-given https://stackoverflow.com/questions/29236556/how-can-i-calcu...
- SuchAnonMuchWow 6y agoStoring a number of the order of magnitude of n! will take the same amount of memory than storing a permutation of n elements, so what's the point ?
- FabHK 6y agoGood point. Storing a number of magnitude n! will take n log n bits, and storing n numbers up to n will also take n log n bit. In other words, good old Fisher Yates, storing the resulting permutation, and a simple lookup is probably the way to go.
- HelloNurse 6y agoIf one really wants to do it the slow and hard way, it's possible to compute a random permutation of n elements one element at a time with n bits of storage (less with fairly generic compression techniques): just remember the set of numbers that have been produced so far and sequentially pick one of the remaining ones. You'll waste some combination of additional memory (for arithmetic decoding state) and random bits (for rejected samples), but materializing a large randomly permuted vector should be slower.