Unrepeated random numbers

Hi.
I'm trying to create a card game for my neice.
My problem is, how do I generate 52 random numbers without any of them being repeated?.
If I use a For - Next loop such as:-

For I=1 to 52
Number(I)=Rand(52)
Next

I get 52 numbers with many of them the same.
Please help if you can.

Fert.

You don't want to generate 52 random numbers, you want to shuffle an array of 52 numbers, slightly different.

as Pert said... but in much more easy to follow sense.

you want to make a list of the 52 cards.

You then shuffle them.... My favorite way is to really shuffle them. 2 ways.

First, take the bottom card and move it to slot 2, then take the bottom card and move to slot 4 then 6 8 10 12 14 16 18...

do that a random number of times.

move the bottom 26 cards to the top. after each shuffle, so you don't have the top card always in the same place.

then do every 3, and then every 7... each for random numbers of times. Then do at least 1 more like the first one to make extra sure it is mixxed up.

Then, deal like the real game, restack the cards as you play so the user's choices effect the random nature of the cards. This will create a truely random deck. As truely random as a real deck of cards is.

This can be used for any kind of card game, even with many decks and with many numbers of cards.


EDIT.. I forgot to say the other way.... generate a random number from 1 to 52 (or however many card you have) thjen take all the card below that number and move them to the top, repeat 1000 times.... this isn't as realistic.. but makes for smaller code.

This is one way to do it if you are using arrays:

Strict

Local deck:Int[52] ' This is our deck of cards.

SeedRnd MilliSecs() ' Make rand() a bit more random

' Fill deck with cards
For Local i:Int = 0 Until 52
	deck[i] = i
Next 

' Shuffle the deck
For Local i:Int = 0 Until 1000
	Local c1:Int = Rand(0,51)
	Local c2:Int = Rand(0,51)
	Local t = deck[c1]
	deck[c1] = deck[c2]
	deck[c2] = t
Next

Graphics 800,600,0,2
SetBuffer BackBuffer()

SeedRnd MilliSecs()

Dim cards_array(52)
For i=1 To 52
	cards_array(i)=i
Next

For i=0 To 2000
	shuffle(Rand(1,52),Rand(1,52))
Next

textX=0 : textY=0

For i=1 To 52
Text textX*50,textY*20, cards_array(i)
textY=textY+1
If textY>12 : textY=0 : textX=textX+1 : EndIf
Flip
Delay 500
Next


WaitKey


Function shuffle(cardA,cardB)
	cards_array(0)=cards_array(cardA)
	cards_array(cardA)=cards_array(cardB)
	cards_array(cardB)=cards_array(0)
End Function

EDIT: Man, you guys so beat me to it.

I tried to make mine do a more realistic shuffle (by doing it the same way a person would).


in bmax:

Global cardsArray:Int[52]

SeedRnd(MilliSecs())'seed the random number generator to help prevent pattern repeating

ResetCards()
Shuffle()

For Local i:Int = EachIn cardsArray
	Print i
Next



Function Shuffle(res:Int = 20)
	Local split1:Int
	Local Split2:Int
	Local Split3:Int
	Local Cut:Int[]
	
	For Local i:Int = 0 To res
		Split1 = Rand(20, 30) 'remove approximately half the pack from the bottom
			Cut = CardsArray[Split1..]
			CardsArray = CardsArray[..Split1]
			
		Split2 = Rand(0, Len(Cut)/2) 'Drop part of that from the top onto the top of the main pack
			CardsArray = ConcatIntArray(Cut[..Split2], CardsArray)
			Cut = Cut[Split2..]
			
		Split3 = Rand(0, Len(Cut)/2) 'drop the next part on top of that
			CardsArray = ConcatIntArray(Cut[..Split3], CardsArray)
			Cut = Cut[Split3..]
		'drop the rest
		CardsArray = ConcatIntArray(Cut, CardsArray)
	Next
End Function


Function ResetCards()
	For Local i:Int = 1 To 52
		cardsArray[i-1] = i
	Next
End Function


Function ConcatIntArray:Int[](Array1:Int[], Array2:Int[])
	Local result:Int[]
	
	For Local count:Int = 0 To Len(Array1)-1
		result = result[..Len(result)+1]
		result[count] = Array1[count]
		
	Next
	
	For Local count2:Int = 0 To Len(Array2)-1
		result = result[..Len(result)+1]
		result[count+count2] = Array2[count2]
			
	Next
	
	Return result
End Function

Yes, my "shuffle" function would be more appropriately named "switch".

There must quite litterally be hundreds of ways to shuffle a deck of cards. Here's my version:

SuperStrict

Type CardDeck
	Field myCards:Byte[52]
	
	Method New()
		For Local i:Int = 0 Until myCards.length
			myCards[i] = i
		Next
	EndMethod
	
	Method shuffle()
		Local n:Byte = 51
		While n > 0
			Local k:Byte = Rand(0,n)
			Local temp:Byte = myCards[n]
			myCards[n] = myCards[k]
			myCards[k] = temp
			n:-1
		EndWhile
	EndMethod

	Function getCard:String( cardNumber:Int )
		Local temp:String
		Select cardNumber / 13
			Case 0
				temp = "Clubs"
			Case 1
				temp = "Diamonds"
			Case 2
				temp = "Hearts"
			Case 3
				temp = "Spades"
		EndSelect
		Return (cardNumber Mod 13) + " of " + temp
	EndFunction
EndType

Local myDeck:CardDeck = New CardDeck
myDeck.shuffle
For Local i:Int = EachIn myDeck.myCards
	Print CardDeck.getCard(i)
Next

I wrote this a while back. It sorts using lists, which apparently use bubble sorting as opposed to a quicksort on array.sort( ), so maybe it should be modified to use arrays.

Strict

Module GameStub.RandomSort

ModuleInfo "Version: 1.00"
ModuleInfo "Author: Michael Reitzenstein"
ModuleInfo "License: N/A"
ModuleInfo "Copyright: Michael Reitzenstein"
ModuleInfo "Modserver: N/A"

Import BRL.LinkedList
Import BRL.Random

Rem

	Randomly sorts arrays And lists
	
End rem


Type TRandomSort

	Function SortArray:Object[]( Array:Object[] )
		
		Return SortList( ListFromArray( Array ) ).ToArray( )
		
	End Function
	
	Function SortList:TList( List:TList )
	
		Local ElementList:TList = New TList
		Local ResultList:TList = New TList
		
		For Local obj:Object = EachIn List
		
			ElementList.AddLast( TRandomSortElement.Create( obj ) )
			
		Next
		
		ElementList.Sort( )
		
		For Local rse:TRandomSortElement = EachIn ElementList
			
			ResultList.AddLast( rse.Value )
			
		Next
		
		Return ResultList
	
	End Function
		
End Type

Type TRandomSortElement
	
	Field Sort = Rand( 1, 262144 )
	Field Value:Object
	
	Function Create:TRandomSortElement( Value:Object )
		
		Local rse:TRandomSortElement = New TRandomSortElement
		
		rse.Value = Value
		
		Return rse
		
	End Function
	
	Method Compare( obj:Object )
		
		Return Sort - TRandomSortElement( obj ).Sort
		
	End Method
	
End Type

fert: of course shuffling is a good idea, but to answer your original question you have to make an array 52 long, then make a random number and loop through the array to check if it is already in there, if not add it. Repeat this until the array is full, but it might be a bit slow at the end as the 52nd slot may take ages to come up with an unused number!

No offence intended, but that made me laugh out loud for real. |oD

Wow what a great response.
Thank you all for your help.
I will try each solution and use the one that suits me best. Being something of a novice, it may take me a little while to understand all the concepts you have put forward. I will try my best.
Thanks again.
Fert

For what it's worth I use:

SeedRnd MilliSecs()

Dim CARD(51),CHECK(51)

Shuffle()

Function Shuffle()


For loop=0 To 51
CHECK(loop)=0
Next

aa=0

Repeat

rr=Rnd(51)
While CHECK(rr)=1
rr=Rnd(51)
Wend

CHECK(rr)=1
CARD(rr)=aa
aa=aa+1

Until aa=52

End Function

You can easily check that it's selecting different cards by using:

For ll=0 To 51
Print CARD(ll)
Next

CHECK simply checks to see if that card has already been used.


Regards

Thanks again for all your help.
I must say a special thank you to BigH. His offered solution is exactly what I need.
Merry Christmas to all.

Regards,
fert

Except it has a best-case quadratic time complexity. Might not be a big deal when you're only dealing with 51 elements tho'.

This one is probably the least efficient of the bunch, but an elegant solution if I may say so myself:

include "vectorC.bb" ; <a href="http://blitzbasic.com/Community/posts.php?topic=53352" target="_blank">http://blitzbasic.com/Community/posts.php?topic=53352</a>
seedrnd millisecs()

function shuffle(deck.vectorC)
	total = vector_count(deck)
	for i = 0 to total-1
		card = vector_remove_element(deck, rand(0, total-i-1))
		vector_push(deck, card)
	next
end function


deck.vectorC = vector_new()
for i = 0 to 52-1
	vector_push(deck, i)
next

shuffle(deck)

for i = 0 to 52-1
	print vector_get(deck, i)
next

P.S. actually, I think I like FlameDuck's better.

What exactly is "a best-case quadratic time complexity" please? If you could give me the answer in easy to understand English I'd appreciate it!!
Regards.

Read up on complexity theory on Wikipedia: http://en.wikipedia.org/wiki/Big_O_notation

EDIT: the "External Link" on that Wikipedia page is probably more relevant and easier to follow: http://www.cprogramming.com/tutorial/computersciencetheory/algorithmicefficiency1.html

In simple terms, it could take 1 try to find a unique number for that final slot or it could take several seconds or even hours. Who knows?

Time complexity is a measure of how much time an algorithm takes to execute for n number of elements. When something is "best-case" it reflects the quickest possible outcome of an algorithm (in the above mentioned example this would be a case where two random numbers are never the same).

Now the best possible time complexity is constant - where an algorithm takes the same time, regardless of how many elements it has. Inserting values into the end or begining of a linked list is a good example of an operation with constant time complexity.

The second best is logarithmic time complexity - where an algorithm takes at most log(n) time to complete. An example of this is the binary search, or "numbers guessing game", where you start in the middle of the range, and then halve if it's lower, or add half if it's higher each time, eventually narrowing it down without having to check all elements.

Way down on the list is quadratic time complexity, where the time taken is n^2. An example of such an algorithm is the bubblesort algorithm. You can usually identify such algorithms by nested 'For' loops. This means that bubblesorting 100 elements takes 10000 time. Bubblesorting 200 elements takes 40000 time, and so on, each time you double your elements, you quadruple the time. As you can probably tell, such routines can quickly grind to a halt when using large data sets.

Now for small values of n (like 52) this discussion is mostly academic, particularly if Rand delivers mostly evenly distributed random numbers, you won't have many misses, although a gausian distributed random function could potentially run "forever".

The most immediate problem with mine is that cards at the front of the array could have a tendancy to stay at the front of the array. Whether this is actually a problem isn't something I've tested to any larger degree, and probably isn't that different from a real world deck of cards.

Thanks for that info. As I write mainly puzzle games I've used that bit of code a lot and never (up until now) had that problem - but then I'm never using large amounts of data either.
Regards

You can also just keep the list and run the list through another list of numbers you created... in other words
1,2,3,4,5,6,7,8,9,10
gets reordered to
2,6,3,9,8,10,1,4,7,5

then, lets say you draw 3 cards... just to be simple.
2,6,3 and then plop them at the bottom of the deck

9,8,10,1,4,7,5,2,6,3

then reorder it with the same list

8,7,10,6,2,3,9,1,5,4

and draw some more cards

8,7,10,6

2,3,9,1,5,4,8,7,10,6

then reorder the list with that same key list.

6,4,9,10,7,6,2,1,8,5


This doesn't use a random number generator at all and generates random numbers. Because it uses the user to seed it's own random number generation system with built in unique numbers.

When you are playing say... poker.. you draw off the 5 starting cards, but then also draw off the cards that the players discard, and it reorders the list as you put the discarded cards at the decks bottom first.



This can be used for millions of unique numbers and only take the time it takes to process 1 unit times that million... so... it is just n times... rather than n^2 times.... is that an acceptable reduction?

Here's another simple one, also using lists.

SuperStrict

Type card
	Field shuffleorder:Int
	Field id:Int

	Method Compare:Int(otherObject:Object)
		Local c:card= card(otherObject)
		If c = Self Return False
	
		If shuffleorder= c.shuffleorder
			Return True
		Else
			Return Sgn(shuffleorder - c.shuffleorder)
		EndIf
	End Method	

End Type


Function List(deck:tlist)

	For Local c:card = EachIn deck
		Print c.id + " - ( " + c.shuffleorder + " )"
	Next	

End Function



Function shuffle(deck:tlist)

	Local randSize:Int = deck.count() * 2

	For Local c:card = EachIn deck
		c.shuffleorder = Rand(randSize)
	Next
		
	deck.sort()

End Function




'--Test Program
' make a deck of cards:

Local c:card
Local deck:tlist = New tlist

For Local n:Int = 1 To 52

	c = New card
	c.id = n
	deck.addLast(c)
Next


Print "Before-----------"
List deck

shuffle deck

Print "After-----------"
List deck

This is a revised version of my code which is slightly shorter and prevents any possibility of locking up the computer.

SeedRnd MilliSecs()

Dim CARD(52),CHECK(52)

Shuffle()


Function Shuffle()

For loop=0 To 51
CHECK(loop)=0
Next

For loop=0 To 51

rr=Rnd(51)

While CHECK(rr)=1
rr=rr+1
If rr=52 Then rr=0
Wend

CHECK(rr)=1
CARD(rr)=loop

Next

End Function

Regards.

This is the "random permutation" problem. As far as I know, the best way to do it is to iterate through every "card" in the "deck", and swap it with a random card between that card and the end of the deck (NOT every card in the whole deck).

For example (where Deck is an array of TCard objects):

For Local i:Int = 0 to Len(Deck)-1
  Local card:TCard = Deck[i]
  Local swapIndex:Int = Rand(i, Len(Deck)-1)
  Deck[i] = Deck[swapIndex]
  Deck[swapIndex] = card
Next

dim Cards(52) '0=card not yet picked, 1=card been 
dim CardsPicked(52) 'array index 1=first card of shuffled deck, array index 52=last card of shuffled deck, array value at index = id number/index of card (ie 9 of hearts) 
picked
;create shuffled deck
For i=1 to 52
Card=rand(1,52)
while Cards(Card)=1 
Card=Card+1
if Card>52 then Card=1
wend
Cards(Card)=1
CardsPicked(i)=Card
next

In that case

Type card
	Field id:Int
End Type

Function Shuffle:tlist(deck:tlist)
	Local ShuffledDeck:tlist = New tlist
	Local o:Object
	
	While deck.count()
		o = deck.ValueAtIndex(Rand(deck.count()-1))
		deck.remove(o)
		ShuffledDeck.AddLast(o)
	Wend

	Return ShuffledDeck
End Function




'--Test Program
' make a deck of cards:

Local c:card
Local deck:tlist = New tlist

For Local n:Int = 1 To 52

	c = New card
	c.id = n
	deck.addLast(c)
Next


'shuffle And list

deck = Shuffle(deck)
list deck

Function List(deck:tlist)

	For Local c:card = EachIn deck
		Print c.id 
	Next	

End Function

[EDIT] changed Shuffle() to use type :object, so that it willl shuffle a list full of anything, not just cards.

*cough* Really? :o>

Actually, his method is a bit different if you read it carefully, in that he picks a card from Rand(n,52), but you pick from Rand(0,52).

I still stand behind the solution from Peter and I... but that depends on whether you consider human like 'bad' shuffling to be a positive or negative!

As the world and his wife is getting in on the act, here's one from the archives (circa 2001)...

Dim deck(51)

SeedRnd MilliSecs()

Graphics 640, 480

setup_deck()

Repeat
    Cls
    shuffle_deck()
    tx = 100
    nc = 0
    p = 0
    
    Text 0, 100, "Card No"
    Text 0, 150, "Value"
    Text 0, 200, "Card"
    Text 0, 250, "Total"
    
    Repeat
        p = p + card_value(deck(nc))
        If (p = 21) And (nc = 1) Then Text 320, 10, "P O N T O O N !", 1, 0
        If (nc = 4) And (p <= 21) Then Text 320, 10, "F I V E  C A R D  T R I C K !", 1, 0
        If p > 21 Then Text 320, 10, "B U S T !", 1, 0
        
        Text tx, 100, deck(nc)
        Text tx, 150, card_value(deck(nc))
        Text tx, 200, show_deck$(deck(nc))
        Text tx, 250, p
        
        nc = nc + 1
        tx = tx + 40
    Until (p => 21) Or (nc = 5) Or (WaitKey() = 27)
Until KeyDown(1)

End

;

Function shuffle_deck()
    For s=0 To 50
        r = Rand(s + 1, 51)
        tmp = deck(s)
        deck(s) = deck(r)
        deck(r) = tmp
    Next
End Function

Function setup_deck()
    For c=0 To 51
        deck(c) = c + 1
    Next
End Function

Function show_deck$(cardval)
    suit$ = "SHCD"
    cardstr$ = ""
        c = cardval Mod 13
        s = Floor((cardval - 1) / 13)
        Select c
            Case 0
                cardstr$ = "A"
            Case 10
                cardstr$ = "J"
            Case 11
                cardstr$ = "Q"
            Case 12
                cardstr$ = "K"
            Default
                cardstr$ = Str$(c + 1)
        End Select
        cardstr$ = cardstr$ + Mid$(suit$, s + 1, 1)
        Return cardstr$
End Function

Function card_value(cardval)
    cv = (cardval Mod 13) + 1
    If cv > 10 Then cv = 10
    Return cv
End Function

Okay, so it uses the same method as denzilwhatisface to shuffle.

The first person to guess which card game I was writing wins a chocolate santa that's had his head bitten off...

um.... snap?

Ah, sorry...I just sold the santa, disguised as an XBox360, on ebay for 500 quid...

Yeah, I'm sure I was told at some point that doing it that way was more uniformly random (though only slightly, probably).

I suppose the question is, do you want a uniformly random shuffling routine, or do you want a realistic one?

The chances of two cards that were grouped together before a real shuffle staying together after the shuffle are fairly high. I know of at least two card tricks that rely on this fact.

Oh. Right. Sorry, I was replying to the first post really, I only skimmed the rest of the thread and didn't really think about real card shuffling.

1Hmm, might be a good idea to have inbuilt uniformly-random shuffling routines for lists and arrays, anyway, though - I can think of other uses. What do people think?

Classic case of overengineering!

He didn't ask how to shuffle, he asked how to get 52 non-repeating random numbers!
(Which we can assume are the numbers 1 thru 52, making our task easier.)

Dim Deck(52)

SeedRnd MilliSecs()

For Loop = 1 to 52
   Repeat
      A = Rand(0, 51)
   Until Deck(A) = 0
   Deck(A) = Loop
Next

You will need to reset all elements of Deck() to 0 if you want to generate a new set of non-repeating numbers.

Hi again all.

In reply to sswift.

That's exactly right, I did ask for a random number generator, and I love your example, thank you.

I fully appreciate all the posts on this subject as I hope to eventually have the expertise to implement all or any of the solutions offered which best suit any future project I may develope.

Best wishes,
fert

Here's a more explanatory, non-Max version of mine:

; Set up the deck
Dim Deck(52)
For i = 1 To 52
  Deck(i) = i
Next


; Shuffle the deck
SeedRnd MilliSecs()
For i = 1 To 51 ; Not 52 since you could only swap the last card with itself!
  card = Deck(i) ; Select each card, in turn
  swapWith = Rand(i, 52) ; Choose a random card to swap it with between this card and the last one
  Deck(i) = Deck(swapWith) ; Swap!
  Deck(swapWith) = card    ;
Next


; Print the shuffled deck
For i = 1 To 52
  Print Deck(i)
Next

actually Sswift... your solution has a major flaw in it...

there are only like 1000 possible decks then. Because seed rand hits up a list of random numbers based on markers... spread out over the list of random numbers. So your deck will be the same if it happens to be generated at the same millisecond.. (If I understand how it is picking the number... that is, based on what thousandth of a second you are at... meaing only 1000 possible number starting points.. and only 1000 decks.)

Mine offeres a truely random number... oddly enough... because it doesn't use the computers random numbers.

Damp, if I understand your one correctly (an arduous task), you don't have any random numbers, which results in the same sequence of cards each time. Unless you are implying that somehow the cards are initialized in a completely random way before calling your routine, in which case, what's the point in your routine?

SeedRnd Millisecs() is about the best way of achieving a reasonably random number in Blitz because the chances of it being called when millisecs() returns exactly the same number is so slim it's not worth worrying about.


Where does yours get the random numbers from then?

The player. Which makes that argument inaccurate, because random numbers are usually generated from values that can expected to be random, such as:
-Mouse Position
-Window Position
-Available Memory
-Number of windows
-System time
etc.

In the end, random numbers can be pretty random... and it's all based on the user. It's not impossible to write your own generator, either.

I'm just being a pain, though. I don't think DampeS8N's idea is explained clearly enough. It sounds to me like you're getting the user to do a bit of the shuffling?

No offense, but are you on crack, or some other mind altering substance? :-)

Millisecs() returns a number between -2 billion and +2 billion. This number depends on how long your PC has been on.
It doesn't return a number between 1 and 1000 depending on where you are within a second or whatever you think it does. It just increments by 1 every millisecond.

So while yes, theoretically millisecs() could generate the same deck, so can shuffling the cards since there are only X number of possible combinations of 52 cards.
I think 4 billion different decks is sufficiently random. :-)

>of course shuffling is a good idea, but to answer your
>original question you have to make an array 52 long, then
>make a random number and loop through the array to check
>if it is already in there, if not add it. Repeat this
>until the array is full, but it might be a bit slow at the
>end as the 52nd slot may take ages to come up with an
>unused number!

Use 2 arrays of the same size and use a variable(source_total) to hold the number of cards in the 'source' array. Then simply move a random card(rnd(1,source_total) could be #25) from the 'source' array to the next sequential slot in the 'destination' array(dest_num, could be #1). Then delete the card from the 'source'(source_array(25)=0), move the cards following the moved card(source_array(26) to source_array(dest_num)), subtract one from source_total and move all following cards in array 1 up by 1 step(source_array(25)=source_array(26) etc).


Andy

Andy: Drop the arrays and use linked lists. Gets rid of having to step through a bunch of 0's. Brings things much closer to O(N) time :)

>Andy: Drop the arrays and use linked lists. Gets rid of >having to step through a bunch of 0's.

There is really no need for 0's in my proposal and you are only processing the actual number of elements in each array. The 0 in my above post is just to make the whole process more transparent and to visualise 'moving' the card from one array to the other.

> Brings things much >closer to O(N) time :)

As far as I recall, arrays are faster than types.

My proposal actually spends less time towards the last part of the shuffle than it does towards the first because The number of elments in destination_array increases and the number of elements in source_array decreases, thus you have less elements to move in source_array.


Andy

sswifts one is good and DampeS8N is crazy but hopefully now rehabilitaed.

Andy's solution sounds identical to mine in principle. I'm making an optimization: instead of two separate arrays, the last N elements of my array is the randomized deck. Essentially - select a random card from the first 52 cards and move it to the end of the deck, select a random card from the first 51 cards and move it to the end of the deck, etc. Of course, I'm also using my vector container library (which uses banks) instead of straight arrays to simplify things (for me, anyway.)

Using linked-list(s) means you'll have to walk the source list every time you want to find the Nth random element. Using array(s) means you'll have to move elements back to fill in your hole when you need to delete one. Both approaches have disadvantages for this application.

denzilquixode solution is the one, all you need to do is swap.

Interestingly enough it's also the solution used in a lot of games to decide what powers ups etc to deliver to the players. It allows for wieghting of random numbers, ie. some things get delivered more often than others.

Take the following sequence "1112344444", if we shuffle it and use the new sequence to determine what powerups we deliver to the player we can always guarantee that 50% of the powerups will be of Type 4, there will always be 3 of type 1 and so on...

Anyway enough rambling, I think I must still be drunk.

That's how I weight the power ups in Xmas Bonus, a list (array) of numbers and repeats are allowed, then a random number is picked that is the array index.

Dim Deck(52)

X = MilliSecs()
If X <= 0 Then X = -X + 1

For Loop = 0 To 51
   X = (2 * X) Mod 53	
   Deck(Loop) = X-1
Next

This algorithm will produce a unique sequence of non-repeating random numbers between 0 and 51 for any given seed. In theory. I ran it 10,000 times to make sure.

>Andy's solution sounds identical to mine in principle.

Sure is, but yours is cleverer :)


Andy

Hm... scratch that.

There's one limitation which I failed to take into account. With this algorithm, X cannot equal or be a multiple of 53. And I suspect that even if you make sure it is not a multiple of 53 that there will only actually be 52 possible decks.

...

Yup, I've just confirmed that. Deck 54 is the same as Deck 1. :-(

Anyway, as for the origin of the algorithm, I learned while reading about random numbers that it is possible to generate non-repeating squences of them. I then found this page:

http://www.brpreiss.com/books/opus4/html/page472.html

Which explains how to generate such a sequence of random numbers. I used the equation at the bottom of the page, which conveniently had a period of M-1 and was unable of producing a 0. This worked out well because 53 is a prime number, and if the period is M-1 because it is impossible to get a 0, then you end up with a period of 52 which is exactly the number of cards we need.

But what the page did not make clear that I have determined by experimentation is that whatever M is is the maximum number of different sets of random numbers you will be able to get.

So if you want a large number sets of of random numbers, the random numbers generated also must be large. And you can't normalize them to 0..1 as suggested at the bottom, because if you do that, then you would end up with some numbers repeating when you converted them back to an integer range.

So that sucks.

But hold on a second... I think I just thought of a way to improve the number of decks you can get.

All you need to do is generate a random number at the start, and then use that to rotate the deck by adding that value to the result, and then doing a mod 52. That would give you 52*52 ... 2704 different possible decks. And it would still be linear time.

This thread gives great insight into why games don't get finished. :)