FASTEST way to make a RND number list, no doubles

[Stellaferox]

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.

 

[agraham]

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

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(0, 52-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

 

[taximania]

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

 

[LineCutter]

Better late posting to this thread than never, even if I was here first
http://www.b4x.com/forum/showthread.php?t=620&highlight=cards

 

[Stellaferox]

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

 

[LineCutter]

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)

 

[Stellaferox]

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

 

[LineCutter]

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

 

[Stellaferox]

@ 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