3 ms·
Maybe someone knows: Is there anyway to generate a list of numbers in random order, containing each number exactly once? i.e. use a random number generator to
by ars 18y ago
Maybe someone knows:
Is there anyway to generate a list of numbers in random order, containing each number exactly once?
i.e. use a random number generator to generate a list of number from 1 to x, containing each number between 1 and x exactly once, but in random order?
The initial purpose I wanted it for was a hard disk burn in test - read every single block on the hard disk in random order, but I need to guarantee I read each and every block exactly once.
Storing the entire array in memory first would use far too much memory.
(It does not need to be cryptographically secure at all, just random.)
Any ideas?
- deleted 18y ago[deleted]
- lincolnq 18y agoI think number theory might help. I don't know much about it, but the way most number generators work (as I understand it) is that they are a representation of a big number which is the internal state, and that internal state completely traverses some large space (2 to some large power) where it hits everything once, and you are only observing a few bits at a time of the value of the internal state. That leads me to think that if you used a small state space (close to size x - maybe the next prime greater than x) you could walk the whole space and hit every number once. Example: take two primes p and q (I think they might only have to be relatively prime), where q >= x. I'll use x=6, p=19 and q=7. Observe multiples of p: 0,19,38,57,76,95,114 Mod them by q: 0,5,3,1,6,4,2,0... Take the first q results, but drop the ones >= x: 0,5,3,1,4,2 If you want a different series, just use a different p. You can skip any number of initial results if you want to start somewhere later in the state space. I guess it's worth noting that selection of p and q makes a difference to how "random" it looks -- if p and q are only 1 apart, it will just count up from 0, etc. I don't have a good intuition for what values produce "random"-looking results. And yeah, this method is definitely not cryptographically secure in any way. (Any number theorists around to tell me this is a stupid idea?) Edit: this isn't that great, because the pattern is obvious (19 == -2 mod 7) so it's equivalent to subtracting 2 each time. Maybe if you pick a q three times the size of your x (15) and still drop the ones greater than x, you could get it to look more "random". Hmm.