programming challenge

[Fusion_power]

And everyone thought this was a "programming problem". Well it was really a puzzle in DISGUISE!

I'll write a program and get this, I will write it in text and not test it until I am finished. We'll see if I can get the shuffle algorithm right the first time. Btw, there are are couple of really good routines for doing this as NickGlover has indicated. Figure out how this shuffle routine works and you will be amazed how many times you can use it when programming.

Note that I will be doing a randomization of the deck which as Wackerbarth indicated is not the same as an actual card shuffle.

One special note for NickGlover, line 3040 could also swap the last element of the array with the selected element and achieve the same result (3040 IF P1 < ZB THEN CARD$(0, P1) = CARD$(0, ZB))

Here is the first installment:

1000 REM *** ENTRY *** (THESE LINES INIT THE SCREEN AND LOAD THE ARRAY)
1010 SCREEN 0
1020 WIDTH 80
1030 COLOR 15,1,1
1040 CLS
1050 DIM CARD$(6, 52) : REM WHERE I'LL PLACE THE CARDS!
1060 FOR X = 0 TO 52
1070 READ CARD$(0, X)
1080 NEXT X
1090 RANDOMIZE TIMER : REM INITS THE RANDOM NUMBER GENERATOR SO IT DOES NOT DUPLICATE ON GAME ENTRY


2000 REM *** MAIN ROUTINE ***
2010 PRINT: PRINT
2020 GOSUB 3000
2030 GOSUB 4000
2040 GOSUB 5000
2060 END


3000 REM *** RANDOMIZE THE CARDS ***
3010 FOR ZB = 52 TO 1 STEP -1 : REM number of items to randomize in a loop counting down to 1
3020 P1 = INT(ZB * RND) + 1: REM pick a random number less than or equal to the number of cards left to sort
3030 CARD$(1, ZB) = CARD$(0, P1): REM move the selected card into the second row of the array
3040 IF P1 < ZB THEN FOR ZA = P1 TO ZB - 1: CARD$(0, ZA) = CARD$(0, ZA + 1): NEXT ZA: REM this is the magic!
3050 NEXT ZB: REM end of the loop


4000 REM *** PAINT THE SCREEN ***


5000 REM *** PLAY THE GAME ***


6000 REM *** CARD LISTING ***
6010 DATA Ace of Spades, 2 Spades, 3 Spades, 4 Spades, 5 Spades, 6 Spades, 7 Spades, 8 Spades, 9 Spades, 10 Spades, Jack of Spades, Queen of Spades, King of Spades
6020 DATA, Ace of Hearts, 2 Hearts, 3 Hearts, 4 Hearts, 5 Hearts, 6 Hearts, 7 Hearts, 8 Hearts, 9 Hearts, 10 Hearts, Jack of Hearts, Queen of Hearts, King of Hearts
6030 DATA, Ace of Diamonds, 2 Diamonds, 3 Diamonds, 4 Diamonds, 5 Diamonds, 6 Diamonds, 7 Diamonds, 8 Diamonds, 9 Diamonds, 10 Diamonds, Jack of Diamonds, Queen of Diamonds, King of Diamonds
6040 DATA, Ace of Clubs, 2 Clubs, 3 Clubs, 4 Clubs, 5 Clubs, 6 Clubs, 7 Clubs, 8 Clubs, 9 Clubs, 10 Clubs, Jack of Clubs, Queen of Clubs, King of Clubs

[c00ler]

Originally Posted by NickGlover

[code:1]for i = 1 to 52
generate random number, r, such that i <= r <= 52
swap the cards i and r
next i[/code:1]

That program shuffles very bad.
Because first card is never on it's place

Originally Posted by apocalypse

Now for the hard question... How do you guarantee that every permutation is equally likely? (Hint: 52! >> 2^64)

Hint is wrong.
There must be (2^64)^52 (there are 52 random numbers)
And 2^3328>10^998>>8.1E67>52!
Moreover: Program can generate all permutations, but they can be not equaly likely.

So it's not only "programming problem"


My solutions
1)O(N) (I suppose that generating random number in the range 1..N takes O(N) time)
All shuffles are stored in constant array.
We just randomly choose one of them.
"+" Shuffles perfectly and very fast
"-" Uses O(N!) RAM

2)O(N*LOG N)

Step 1: generate array of 52 different random numbers
Step 2: Sort the cards with heapsort (it's O(N*LOG N)in the worst and in average case) in ascendancing order by these random numbers

How to generate 52 different random numbers:
Random_#i=random(1..N*LOG N)*100+i
( 100 must be replaced with 10^(Log10(N)+1) )

"+" uses O(N*LOG N) RAM
"-" shuffles not perfectly for small N because probability Random_#N>Random_#1 is greater than 0.5, for big N it's closer to 0.5

[Maybeso]

The stratagy for most of the ideas posted so far is to pick the cards in a random order and deal them to the 4 hands in proper order.

A trick that bridge programs have been using for years is to deal the cards in proper order, but deal them to a random hand (until each hand is 'full').

The magic is, the program does not have to shuffle the cards -- plus, the 4 hands each receive 13 cards in proper order, so the hands are already sorted by suit and by rank!

This works for bridge because all of the cards are dealt. To adapt the idea to this puzzle, I defined the left-over 32 cards as a fifth hand. Here is the outline:[code:1]deck = (As, 2s, .., Ks, Ah, 2h, ..., Kd); * define the deck of 52 cards.
hand = ("","","","","")
max = (5,5,5,5,32)
total = (0,0,0,0,0)
For c = 1 to 52
Repeat
h = Int(Rnd(52)/5) + 1; * this gives a 5/52 chance for each hand,
If (h > 4) Then h = 5; * this gives a 32/52 chance for the stack.
Until total(h) < max(h)
total(h) = total(h) + 1
hand(h) = hand(h):" ": deck(c)
Next c[/code:1]
This generates 4 hands of 5 cards plus the undealt stack of 32 cards.
Each of which is sorted by suit and by rank.
That is the one drawback, the stack is also sorted, giving the impression this method is less random than others.

I realize this solution does not satisfy many of the original conditions, but it does generate 4 random hands.

[Wacky]

Originally Posted by c00ler

That program shuffles very bad.
Because first card is never on it's place

Sure it is 1/52 of the time. remember that you can swap a card with itself. (a no-op).
The first card will remain first each time the initial random number comes up 1.

Originally Posted by c00ler

Hint is wrong.

I don't see that it is wrong.

There are only 52! possible ways to arrange a deck.
Assuming truly random numbers, all of those possible ways are equally likely to be generated by Nick's algorithm.

A pseudo-random number generator always generates the same sequence from its initial seed.

If the seed has 64 bits, it can generate at most 2^64 possible sequences.
Since 52! > 2^64, some of the sequences would not be generated.

PS:
I certainly don't follow the rest of your argument. Perhaps you can re-explain it.

[apocalypse]

I was just remarking that truly random numbers are hard to come by, especially in a short term programming contest. In that case, as Wackerbarth noted, the number of card permutations computable by a given algorithm with a given (standard) pseudo random number generator is significantly less than the number of permutations of a deck of cards.

Hence in a typical solution, each permutation is equally probable, but some are more equal than others. :)

[Xyzzy]

Warning... Thread hijack...

I've always wondered about how random the random number generator on a computer is... (Apparently, not very random!)

Anyways, how do we measure how random something is?

This web page is somewhat interesting...

http://home.t-online.de/home/p.westphal/zran_eng.htm

[ColdFury]

I've always wondered about how random the random number generator on a computer is... (Apparently, not very random!)

Well, it depends on the algorithm the particular program is using, of course.

[cheesehead]

Originally Posted by Xyzzy

I've always wondered about how random the random number generator on a computer is...

See the first 190 pages of Knuth's The Art of Computer Programming, Volume 2: Seminumerical Algorithms for discussion of random numbers and pseudorandom number generators.

(Apparently, not very random!)

Some pseudorandom number generators are much, much better than others.

Anyways, how do we measure how random something is?

Also covered by Knuth.

This web page is somewhat interesting...

http://home.t-online.de/home/p.westphal/zran_eng.htm

For those who haven't followed the link, it's a connection to a physical random number generator. Physical random number generators are theoretically superior to software pseudorandom number generators, but the devil's in the details.

[c00ler]

Originally Posted by Wackerbarth

Sure it is 1/52 of the time. remember that you can swap a card with itself. (a no-op).
The first card will remain first each time the initial random number comes up 1.

Oops ops: . It shuffles perfectly.(I can prove it)

Originally Posted by Wackerbarth

A pseudo-random number generator always generates the same sequence from its initial seed.

If the seed has 64 bits, it can generate at most 2^64 possible sequences.
Since 52! > 2^64, some of the sequences would not be generated.

But why we must use only 1 seed for all numbers?
We can generate 52 random seeds to generate (2^64)^52 random sequences.
Only problem is that random with random seed must be random number generator.

Originally Posted by Wackerbarth

PS:
I certainly don't follow the rest of your argument. Perhaps you can re-explain it.

I consider program to be a good shuffler iff probability of getting any shuffle is 1/(n!), or in that puzzle 1/(52!)
And NickGlover's program is a good shuffler.

So my argument is somethung like this:"There are shufflers that all 52! probabilitys is nonzero but nonequal, so they are bad shufflers."

[Wacky]

Originally Posted by c00ler

Oops ops: . It shuffles perfectly.(I can prove it)

But why we must use only 1 seed for all numbers?
We can generate 52 random seeds to generate (2^64)^52 random sequences.
Only problem is that random with random seed must be random number generator.

Using a pseudo-random number generator to generate multiple seeds does no good because those seeds are not independent.

If the initial PRNG has a seed of 64 bits, you still get, at most, 2^64 possible results.

Originally Posted by c00ler

And NickGlover's program is a good shuffler.

Therein lies the misunderstanding. I thought that you were claiming the it was not a good shuffler.

[c00ler]

Originally Posted by Wackerbarth

Using a pseudo-random number generator to generate multiple seeds does no good because those seeds are not independent.

If the initial PRNG has a seed of 64 bits, you still get, at most, 2^64 possible results.

Ok, we must use 52 time-based seeds and/or hardware PRNG.
The way to do it is to choose the seed just before generating the next random number.
Also we need to run for example prime95 to randomize the times seeds are generated.

Originally Posted by Wackerbarth

Therein lies the misunderstanding. I thought that you were claiming the it was not a good shuffler.

I was... But it was a mistake.