FASTEST way to make a RND number list, no doubles

Discussion in 'Questions (Windows Mobile)' started by Stellaferox, Jan 30, 2008.

  1. Stellaferox

    Stellaferox Active Member Licensed User

    Hi guys,

    What would you think is the fastest way to generate a list of random numbers, without any doubles.
    At the moment I am using the following loop:

    do
    generate random number
    do
    check whether number is in arraylist "uniques" (building if not)
    if so EXIT and repeat generate random numberloop
    until noDoubles
    UNTIL all numbers are generated

    I want to use this for shuffling a deck of cards, but then a million times to simulate the probability of certain "hands" in poker.

    thnx in advance

    Marc

    PS: I had a thread a while ago concerning this problem but never tried to improve the speed.
     
  2. agraham

    agraham Expert Licensed User

    I don't think you can get much faster than this. It doesn't generate unwanted random numbers. Every generated number is valid.

    Code:
    Sub Globals
       
    'Declare the global variables here.
       Dim Deck(52' holds the shuffled cards
    End Sub

    Sub App_Start
       AlCards.Clear 
    ' ArrayList - clear in case used before   
       For i = 0 To 51
          AlCards.Add(i)   
    ' stick all the cards in the array list
       Next
       
    For i = 0 To 51
          r = 
    Rnd(052-i)
          Deck(i) = AlCards.Item(r) 
    ' add card to deck
          AlCards.RemoveAt(r)   'remove it from array list
       Next
       
    For i = 0 To 51 ' this bit just for display
          msg = msg & " " & Deck(i)
       
    Next
       
    Msgbox(msg)
    End Sub
     
  3. taximania

    taximania Well-Known Member Licensed User

    In an earlier project of mine, (ahem) ;)

    I picked 2 random numbers and swapped the array contents.

    eg.

    Dim Deck(52)
    temp=0
    b=0
    c=0

    For a = 1 to ?? 'as many times as you want.
    b=rnd
    c=rnd
    temp = deck(b)
    deck(b)=deck(c)
    deck(c)=temp
    next a

    This would work for shuffling the cards.
    Not sure it answers your question though :(
     
  4. LineCutter

    LineCutter Active Member Licensed User

  5. Stellaferox

    Stellaferox Active Member Licensed User

    Hi Linecutter,

    Thnx for your answer. I remember the thread (think I started it) and I used your solution in a different program. Now I wanted to know what the fastest way (after compiling) would be, as I like to use this in a simulation.
    Marc
     
  6. LineCutter

    LineCutter Active Member Licensed User

    I don't think that you can do better than agraham's (or mine) for the "player vs. computer" scenario. Then again if you are going to do a million simulations you could probably take some shortcuts...
    • Just draw a "hand" of cards from the unshuffled pack, rather than shuffling & then drawing a hand
    • Only compare suits if they are going to matter (most hands will be determined by face value & not sets of the same suit)
     
  7. Stellaferox

    Stellaferox Active Member Licensed User

    Thanks, that is surely one approach that will work. I thought of creating a limitless gigantic "deck" and drawing hands from that and then discard the hands that hold thesame cards. Maybe that would speed up the process.....
    Marc
     
  8. LineCutter

    LineCutter Active Member Licensed User

    I don't think that that's going to help...

    [A couple of assumptions: you are drawing 2 hands to see which wins vs the other & that there are 52 unique cards in the raw materials (deck) for each hand of the competition)]

    The chance of a duplicate card, in a 2*5 card game is: 1/51 + 1/50 + ... 1/42. Very roughly that's 10%. i.e. you'll have to redraw 1/10 of your hands, plus 1/10 of those.

    That would mean that 1/9 of all attempts to play would be invalid, or alternatively 1.111111 times more attempts are required in order to complete your run than if you'd adopted a more foolproof method of drawing a hand.


    You will probably gain more from streamlining your question than speeding up the iterations...

    Reference points:
    My own software (in <ahem> another basic & archery related)

    MonteCarlo Method
    Bootstrapping
     
  9. Stellaferox

    Stellaferox Active Member Licensed User

    @ Linecutter,

    yes you're right of course. Your assumptions are correct. I thought that being "off" a percent or two wouldn't matter for a guess in winning probabilities. But then, as ever, I want to make it perfect first, then maybe "cheat" later....gaining speed.
    BTW: very interesting software you have there. I am a great fan of simulations, statistics etc.
    At the moment I am programming dealing hands and an evaluation routine for the dealt hand. Then I will make some tables for faster access and computing probabilities by doing simulations. i have to give in some to compensate for the lack of speed on a ppc here I think.
    Thnx
    Marc
     
Loading...