Beefy Boxes and Bandwidth Generously Provided by pair Networks
Keep It Simple, Stupid
 
PerlMonks  

Re^7: How to generate different random numbers?

by thor (Priest)
on Sep 08, 2004 at 12:02 UTC ( [id://389318]=note: print w/replies, xml ) Need Help??


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

Any time discussions turn to randomness and such, someone will use that discussion for security related purposes at some later date. That having been said, I feel that it's my duty as an upstanding netizen to bring to light the implications of certain things. On we go...
Therefore, a random shuffle (or multiple random shuffles, depending on the desired cardinality) can be transformed algorithmically into a random number
Unless you enumerate all of the permutations of the set, I don't know how this could possibly work. Even if you are, you're reducing the size of your output number drastically.

There are n! ways to permute a set of n items. There are n**n ways to choose n items from a set of n with replacement. The limit as n tends to zero of n!/n**n is zero. What this means is that compared with the cardinality of just choosing n random numbers from 1 to n, generating a random number with from a random shuffle gets progressively worse for larger n. This would imply (well, to me anyways) that if you're looking for a random number, better to do it directly than to first shuffle and then transform that shuffle into one.

A random number need not necessarily be chosen from an infinite set
Point conceded. I mis-spoke.

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

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

Replies are listed 'Best First'.
Re^8: How to generate different random numbers?
by Pragma (Scribe) on Sep 08, 2004 at 18:16 UTC
    Unless you enumerate all of the permutations of the set, I don't know how this could possibly work.
    That's exactly what I'm doing; there is no need to limit yourself to individually selected numbers. If you treat each shuffled set as a random selection from the set of all possible shuffles, then you have a perfectly good random number, equivalent to a randomly selected integer from 1 to N!. If you do M shuffles, you can select random numbers from a set of size N! ^ M. It doesn't take a very large N and/or M to reach the cardinality needed from cryptographic applications.
      This works in theory. I think that it would become pretty unwieldy in practice though. Given a permutation of a set (let's say {5 1 3 2 4}), which permutation is that of {1 2 3 4 5}? The fourteenth or the forty-second? Wouldn't you have to pre-compute and store all of the permutations for this to work?

      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

        Yes, in practice, it would be absurd. I never claimed that this would be a good way to generate random numbers. I was merely responding to the misguided belief that a random shuffle was somehow any less random than a random selection from a finite set. It is not, and the theoretical ability to generate random numbers from a shuffle is what proves the point. QED, etc etc.

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://389318]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others making s'mores by the fire in the courtyard of the Monastery: (4)
As of 2024-04-20 04:05 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found