Create a random permutation of 1..N in constant space

by

The easiest way is probably to just create a full-range PRNG for a larger range than you care about, and when it generates a number larger than you want, just throw it away and get the next one.

Another possibility that’s pretty much a variation of the same would be to use a linear feedback shift register (LFSR) to generate the numbers in the first place. This has a couple of advantages: first of all, an LFSR is probably a bit faster than most PRNGs. Second, it is (I believe) a bit easier to engineer an LFSR that produces numbers close to the range you want, and still be sure it cycles through the numbers in its range in (pseudo)random order, without any repetitions.

Without spending a lot of time on the details, the math behind LFSRs has been studied quite thoroughly. Producing one that runs through all the numbers in its range without repetition simply requires choosing a set of “taps” that correspond to an irreducible polynomial. If you don’t want to search for that yourself, it’s pretty easy to find tables of known ones for almost any reasonable size (e.g., doing a quick look, the wikipedia article lists them for size up to 19 bits).

If memory serves, there’s at least one irreducible polynomial of ever possible bit size. That translates to the fact that in the worst case you can create a generator that has roughly twice the range you need, so on average you’re throwing away (roughly) every other number you generate. Given the speed an LFSR, I’d guess you can do that and still maintain quite acceptable speed.

More Related Contents:

  1. Unique (non-repeating) random numbers in O(1)?
  2. Expand a random range from 1–5 to 1–7
  3. Is there an efficient way to generate N random integers in a range that have a given sum or average?
  4. What distribution do you get from this broken random shuffle?
  5. Select k random elements from a list whose elements have weights
  6. Data structures for loaded dice?
  7. Pseudorandom Number Generator – Exponential Distribution
  8. Choosing n numbers with fixed sum
  9. Shuffle list, ensuring that no item remains in same position
  10. True random number generator [closed]
  11. Creating a random number generator from a coin toss
  12. Given a number, produce another random number that is the same every time and distinct from all other results
  13. Random points inside a parallelogram
  14. Reservoir sampling
  15. Generating shuffled range using a PRNG rather than shuffling
  16. Randomly choosing from a list with weighted probabilities
  17. A Good and SIMPLE Measure of Randomness
  18. Unbiased random number generator using a biased one
  19. Complexity of absolute difference and sum
  20. C++ Sorting Algorithms [closed]
  21. How to compute Discrete Fourier Transform?
  22. Difference between Big-O and Little-O Notation
  23. Diff Algorithm? [closed]
  24. Rounding to an arbitrary number of significant digits
  25. Store the largest 5000 numbers from a stream of numbers
  26. search for interval overlap in list of intervals?
  27. robust algorithm for surface reconstruction from 3D point cloud?
  28. Are there any cases where you would prefer a higher big-O time complexity algorithm over the lower one?
  29. How to implement tag system
  30. how do I create a line of arbitrary thickness using Bresenham?

Leave a Comment