4 ms·

Could someone explain how this works? I feel like unique shuffling given a random seed is very useful algorithm, but I can't follow this code because of the var

• throwaway_yy2Di 11y ago
  The general idea is to draw n uniform samples from [1..N] and return them in sorted order. You can generate these incrementally, in order (no sort needed). The mean difference between successive samples is ~N/n. If the samples are uniformly distributed, their differences should have roughly an exponential [0] distribution (if N, n are large). So the inductive step is: given k'th sample a[k], let a[k+1] = a[k] + S, where S is drawn from a discrete exponential distribution with mean 1/λ = N/n. That's the `exp(log(rand()) * stuff)' part of the code. This almost works; there's more details [1] if you want it to actually work, and have accurate statistics, not overflow N, etc. [0] https://en.wikipedia.org/wiki/Exponential_distribution https://en.wikipedia.org/wiki/Exponential_distribution [1] https://hal.archives-ouvertes.fr/file/index/docid/75929/filename/RR-0624.pdf https://hal.archives-ouvertes.fr/file/index/docid/75929/file...