Beefy Boxes and Bandwidth Generously Provided by pair Networks
XP is just a number
 
PerlMonks  

Re: Random Math Question

by Roy Johnson (Monsignor)
on Oct 10, 2005 at 22:12 UTC ( [id://498962]=note: print w/replies, xml ) Need Help??


in reply to Random Math Question

I may have misunderstood your suggestion, but it seems to me like your method would always keep elements in each group together. They'd be shuffled with respect to each other, but in a continuous block. To get them to migrate and intermingle, you'd want to split each group in half and shuffle the half-size groups, then shuffle the members of (not-half-size) groups.

I think MJD's objection to the generator is that, if you're shuffling 100,000 elements, you need a generator that can give you a random number between 1 and 100,000. If your generator doesn't have that, you can start with two random numbers, and use them as separate seeds. Each time you need a big random number, you get two small ones (which also become your two new seeds). You combine the two small random numbers into one big random number.

You can do tricks (skip a number occasionally) to keep them from having synchronized repetitions, and you can vary your method of combining them, to help eliminate patterns.


Caution: Contents may have been coded under pressure.

Replies are listed 'Best First'.
Re^2: Random Math Question
by Limbic~Region (Chancellor) on Oct 10, 2005 at 22:29 UTC
    Roy Johnson,
    Since the groups themselves are getting shuffled as well, any 1 of the 100K numbers could end up in any position in the entire range. I had considered the selection of the groups each iteration to also be random but didn't think it was worth it. I didn't really think my position was correct.

    I could have had the characterization of the problem wrong as I did come in on the tail end of it. My understanding was that you already had a list of 100K numbers and you needed to randomize the order. In this case, the numbers themselves don't matter just their positions. My process would be to apply the Fisher-Yates shuffle many times but on different scales. Sometimes using chunks of the list as though they were single elements and sometimes as though each chunk were the entire list.

    Cheers - L~R

      Although any number can end up in any position, without something to break up the groups between repetitions, the groups of numbers will remain grouped:


      Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
      Lingua non convalesco, consenesco et abolesco. -- Rule 1 has a caveat! -- Who broke the cabal?
      "Science is about questioning the status quo. Questioning authority".
      The "good enough" maybe good enough for the now, and perfection maybe unobtainable, but that should not preclude us from striving for perfection, when time, circumstance or desire allow.
        Just to elaborate on what BrowserUK said — It isn't enough for any given number to have an equal probability of ending up in any position. It has to have an equal probability of ending up in any position irrespective of the positions of any other numbers. Clearly, under this algorithm, the number 1 will never be more than b-1 places away from 2 (where b is the block size). (In fact the constraint is tighter than that, but that's enough description to make the point.)
Re: Random Math Question
by Dominus (Parson) on Oct 11, 2005 at 01:16 UTC
    Said Roy Johnson:
    I think MJD's objection to the generator is that, if you're shuffling 100,000 elements, you need a generator that can give you a random number between 1 and 100,000. If your generator doesn't have that, you can start with two random numbers, and use them as separate seeds.
    No, that really wasn't my objection at all.

Log In?
Username:
Password:

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

How do I use this?Last hourOther CB clients
Other Users?
Others lurking in the Monastery: (5)
As of 2024-03-29 13:35 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found