Beefy Boxes and Bandwidth Generously Provided by pair Networks
Pathologically Eclectic Rubbish Lister
 
PerlMonks  

Re^2: How to generate different random numbers?

by Pragma (Scribe)
on Sep 04, 2004 at 23:42 UTC ( [id://388542] : note . print w/replies, xml ) Need Help??


in reply to Re: How to generate different random numbers?
in thread How to generate distinct random numbers?

No he doesn't. What he's actually asking for is a random shuffle. There are well known O(n) time and memory algorithms for that sort of thing. Look up Fischer-Yates.

update: of course a shuffle won't work so well if the range is large

  • Comment on Re^2: How to generate different random numbers?

Replies are listed 'Best First'.
Re^3: How to generate different random numbers?
by thor (Priest) on Sep 05, 2004 at 09:10 UTC
    No he doesn't.
    I'm going to go ahead and disagree with you there, cowboy. Any time you impose a restriction on random, you've made it not random. A random shuffle of a known interval isn't a set of random numbers. Woe unto he who uses the "random" numbers for cryptographic purposes.

    thor

    Feel the white light, the light within
    Be your own disciple, fan the sparks of will
    For all of us waiting, your kingdom will come

      Well since we're just arguing semantics, indeed, a random shuffle of a known interval isn't the same thing as a set of random numbers. But I never said they were the same thing. I merely said that it is not any "less random", and indeed it isn't.

      A random shuffle is really a random selection from a uniform distribution of the set of all possible permutations on that range of numbers (or N!).

      And who said the numbers had to be used for cryptographic purposes? You're adopting a very narrow view of things to make your case, pilgrim.

      Any time you impose a restriction on random, you've made it not random.
      Well this is just plain false (eg. if I restrict myself to a set of random even numbers, the numbers I've chosen are still random, and indeed, no less random). I think what you meant to say is that for cryptographic purposes, random numbers should only be chosen from a uniform distribution. This is an arguable proposition, especially since many distributions can be translated into one another, and thus any cryptographic function can transform a non-uniform distribution into a uniform one.
        A random shuffle is really a random selection from a uniform distribution of the set of all possible permutations on that range of numbers (or N!).
        This assumes that you're chosing one member from the interval. However, even this has a gotcha or two. If you do this on a large scale, an attacker will surely notice that all of your "random" numbers come from the same interval and exploit this fact.

        Moreover, in terms of randomness, a random shuffle and just choosing a random number are vastly different. One is chosing a member from an finite set without replacement, the other is chosing a member from an infinite set with replacement. That is to say that in the true random case, you are just as likely to pick the number that you just picked as you are any other number. In the random shuffle situation, you are guaranteed that this is not the case. An attacker can exploit this, too. For instance, let's say that the interval was [1,4]. As the attacker, you have this knowledge. Furthermore, you've observed, the following numbers go by: 2, 4, 1. What's the next number in the sequence?

        And who said the numbers had to be used for cryptographic purposes?
        Is there any other use? ;)

        thor

        Feel the white light, the light within
        Be your own disciple, fan the sparks of will
        For all of us waiting, your kingdom will come