programming challenge

[Fusion_power]

The challenge is to write a short routine that will shuffle a deck of cards and deal 4 hands of 5 cards each. The deck must start in numerical order by suite (i.e. Ace, 2, 3, ... King of spades) and must be shuffled into random order. Then the 4 hands should be dealt and MUST NOT duplicate any cards already dealt. The code should display the 4 hands of 5 cards individually and then display the remaining stack of 32. No jokers, pun intended!

I'll write my solution over the next hour and try to post it later this evening.

Fusion

Addendum, You don't have to do graphics as in draw pictures of the cards, just a text representation is fine.

[Kevin]

If the TI calculators had a pop function for lists (remove any arbitrary element) this would be easy. But here's how I'd compensate. You'd have a list 1-52, and say 1=ace of diamond, 2-2 of diamonds up through the deck. Then you pick randint from 1-52, store in list 1. Then make whatever element you just picked 0, then pick another random integer 1-52. If that element of the list is not 0, add it to list one. If it's zero, pick another number. Do that for 5 number for list one, 5 for list 2 etc. Sort each list and display.

Instead of shuffling the deck, you pick a card from a random spot within the deck. Works the same, but not exactly what you asked for :? . Crap, just do the same thing for list 5 until you deal the rest of the cards so it'll be in random order. Maybe I should learn a programming language besides Ti basic.

[NickGlover]

I'll add an additional challenge:

The shuffling algorithm Kevin plans to implement will run in O( N^2 ) (N is the size of the deck) average case and O( infinity ) worst case (since it depends on choosing the "correct" random number to complete).

As Kevin noted, the ability to remove any arbitrary element from a list allows better solutions which will generally run in O( N^2 ) average and worst case. (The best I could think of runs more specifically in O( N(N-1)/4 ) average and O( N(N+1)/2 ) worst case.)

My challenge is: Can you find a shuffling algorithm that runs in better than O( N^2 ) for the average and/or worst cases? Examples of better than N^2 include O( N ), O( N^1.7 ), O( N*LOG N ).

[Wacky]

Since this has gotten away from the traditional "puzzle" (and I am as guilty as the next), I'm going to make a public reply.

First, I would not strictly call the act of randomizing the order of the deck "shuffling". A shuffle is a non-random intermixing of the cards.

Second, addressing the act of "randomizing" the order of the cards in the deck, as Nick notes, the wrong algorithm can cause disasterous run times. I would suggest the following approach

Generate the sorted deck as a list.
Select a random element of the list as the first card.
Enter the selected card onto a new list which is the randomized deck.
Remove the card from the sorted deck list.
Repeat (with a deck of N-1 remaining cards).

Now, the speed of the operation depends on how you store the list that represents the deck. Let k represent the number of cards remaining at each step.

If you choose a linear list, and strictly follow the description, each "remove the card" would take k/2 operations to ripple the cards down to fill the hole.

You could use a tree structure instead. Here, the cost is O(log k) per card.

However, I think that we can "cheat" and accomplish the same result.

Store the unrandomized cards in an array.
Select a random array position and provide that card.
Fill the "hole" with the last card in the array.

I believe that this gives a solution of O(1) for each step and O(N) for the whole task.

There are some other "cheats" that might be applied.
For example, in order to simply print the hands as required, we can just "deal" one card at a time directly to the printout without actually placing them in hands or following the standard dealing practice of giving only one, (or sometimes 3, depending on the game) to each player before returning to give an additional card to the first player.

[S80780]

A simple O(N) algorithm to do this is the following:

Choose a random integer s with e.g. 3 <= s <= 10. Repeat a) , b) and c) s times.
a) Choose a random integer k with 1 <= k <= N / 2.
b) Exchange the 1 + i. and the k + i. card of the deck for all 0 <= i <= k.
c) Afterwards choose randomly between 0 and 1. If you chose 1, insert the N - 2k unexchanged cards in front of the exchanged ones.
(Alternatively exchange the i. and the N - i + 1. card of the deck for all 1 <= i <= N / 2)

The Insert - method in c) should be used, if the deck is represented as a single linked queue. If the deck is represented as an array, either method can be implemented effectively.

Benjamin

[NickGlover]

Originally Posted by Wackerbarth

You could use a tree structure instead. Here, the cost is O(log k) per card.

This is the method I was thinking of when I wrote the above post. After I implemented this method, I realized that it could be done in O( N ).

Originally Posted by Wackerbarth

Store the unrandomized cards in an array.
Select a random array position and provide that card.
Fill the "hole" with the last card in the array.

I'm not entirely certain I follow your answer, but it sounds similar to my O( N ) one. I'll psuedocode it which is probably easier than explaining it.

[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]

I really felt dumb when I realized how simple the O( N ) algorithm is. I had just spent a couple hours writing a modified version of a binary tree and working the bugs out of the somewhat complicated O( N*LOG N ) shuffling algorithm.

[Wacky]

Yes, Nick, our procedures are equivalent. I was thinking in terms of moving the selected card off to some destination and having an array of the undealt cards where the upper limit decreases. However, that is equivalent to your using one array with the dealt cards at one end and the undealt cards at the other.

[apocalypse]

That is pretty much the canonical linear shuffling algorithm. In C/C++ you'd iterate from 51 down to 0 because it's slightly cheaper to generate random indices in the range [0, k) than in the range [k, n).

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

[Wacky]

Originally Posted by apocalypse

How do you guarantee that every permutation is equally likely? (Hint: 52! >> 2^64)

Here, I assume that you are referring to the fact that pseudo-random sequences cannot generate more different permutations that there are possible seeds.

There are two ways to overcome this difficulty. (1) Use a bigger seed, or (2) don't use a pseudo-random number generator.

[trif]

[code:1]
CREATE TEMPORARY TABLE rank
(
name VARCHAR(2)
);

CREATE TEMPORARY TABLE suit
(
name VARCHAR(8)
);

CREATE TEMPORARY TABLE deck
(
rank VARCHAR (2),
suit VARCHAR(8),
position FLOAT
)

INSERT rank.name VALUES('A','1','2','3','4','5','6','7','8','9','10','J','Q','K');
INSERT suit.name VALUES('spades','hearts','diamonds','clubs');

INSERT deck.rank,deck.suit SELECT rank.name, suit.name;
UPDATE deck SET position=RAND();
SELECT deck.rank,deck.suit ORDER BY deck.position LIMIT 5;
SELECT deck.rank,deck.suit ORDER BY deck.position LIMIT 5,5;
SELECT deck.rank,deck.suit ORDER BY deck.position LIMIT 10,5;
SELECT deck.rank,deck.suit ORDER BY deck.position LIMIT 15,5;
SELECT deck.rank,deck.suit ORDER BY deck.position LIMIT 20,32;
[/code:1]

[Wacky]

Trif,

Your solution works just fine.

But how do you expect our BASIC friends to even read it?
I suspect that it is just as "greek" to them as if you had used the Symbol font to obscure the code. smile

It's not an O(N) solution, but when N is small, sometimes the best algorithm for large N is inferior to alternatives.

(I had been tempted to post a solution in Lisp, but Nick brought up the question of the speed and I didn't see an easy way to express it without running the complexity up)