2

More specifically, is there an algorithm that can generate, deterministically, provided a seed, n integers from 0-(n-1), with no duplicates or missing numbers, in linear or sub-linear time and constant space?

All the answers i've found or seen online require linear space, as they need to store information about every digit in the sequence before they can give the first number at all. This becomes unreasonable memory usage in the millions/trillions of possible numbers, which is useful for random id generation. Is there an algorithm, say an iterative formula, which nicely spits out one number after another, without having to know any information about all the numbers before it or after it? Or am I living in a pipe dream right now?

Maurdekye
  • 3,597
  • 5
  • 26
  • 43
  • related https://stackoverflow.com/questions/10054732/create-a-random-permutation-of-1-n-in-constant-space – hilberts_drinking_problem Dec 03 '18 at 00:55
  • so you need to solve a unique polynomial equation to find a specific one, but they exist for every n bits? – Maurdekye Dec 03 '18 at 01:01
  • that sounds like something you could make a cryptocurrency about – Maurdekye Dec 03 '18 at 01:01
  • This way out of my field but I doubt that generating every permutation based on a seed is possible without O(N) space. You would need at least N! different seeds, so the largest seed would need at least log(N!) = O(N^2) bits of space. I may be totally wrong on this. – hilberts_drinking_problem Dec 03 '18 at 01:20
  • that's true, but the seeds are not n digits, they are n bits, which means each consecutive seed represents a number range twice as large as the last, so the actual space complexity per n digits is something closer to linear or even logarithmic time – Maurdekye Dec 03 '18 at 01:35
  • Linear Congruential Generator could do that if three requirements of the Hull–Dobell Theorem are satisfied. Though if it is not power of 2, it might require special support lib for modulo. – Severin Pappadeux Dec 03 '18 at 06:33
  • Link to LCG: https://en.wikipedia.org/wiki/Linear_congruential_generator – Severin Pappadeux Dec 03 '18 at 13:54

0 Answers0