20 Sep, 2010, Runter wrote in the 1st comment:
Votes: 0
I started out designing a proper card shuffling algorithm with equal distribution given equal distribution random numbers.

I was successful but later I decided to go a different route. Currently I have a constant matrix representing all possible shuffled decks. Then to get a shuffled deck I simply select a random number between the range of 0..n-1 where n is the number of permutations.

The benifit of this is there is no shuffling process and logging many hand histories of entire decks becomes dramatically easier since an entire deck can be represented by a single number. Also this approach guarentees a perfect distribution in shuffling. The only determining factor would be how well the rng actually works. (which some testing and analyzing would quickly uncover.)

The worst part of this approach is the memory requirement overhead. I feel for a server the additional 140k or so of memory is trivial. Additionally if the server was popularly used it would save memory on individual representation of decks. Particularly because you only need to know how many cards are drawn from the deck. Not the full representation.

Any ideas or thoughts on what I'm doing here is appreciated.
20 Sep, 2010, quixadhal wrote in the 2nd comment:
Votes: 0
Hmmm, well, I'm sure there's a nice complex math way to do this. Here's what I'd use.

#!/usr/bin/perl -w
use strict;
use Time::HiRes qw(time gettimeofday);

sub genDeck {
my ($sec, $usec) = gettimeofday();
my $seed = shift || int(rand($sec + $usec ^ $$)); # Or whatever number you like…
my @cards = split //, "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
my $deck = undef;
srand($seed) if defined $seed;

for(my $i = 51; $i >= 0; $i–) {
my $choice = int(rand($i+1));
$deck .= $cards[$choice];
splice(@cards, $choice, 1);
}
my $output = sprintf "% 16d %s\n", $seed, $deck;
return $output;
}

print genDeck();
print genDeck(42);
print genDeck();
print genDeck(42);

$ perl card_decks.pl
1221670608 CfYXvUjqABboizcmekGtKuhPlsHMWQNROwLxVIyJardpnESFTDgZ
42 mRFWDtaZkrXecBpgwVbUSNxCuzqKIGOlEPQhsLonJAfdvyHYiMTj
245798749 NWevosPSaktybMzJCFYQRcIgnlrTjOGUhXiVAmDfKwLEHuqxBZpd
42 mRFWDtaZkrXecBpgwVbUSNxCuzqKIGOlEPQhsLonJAfdvyHYiMTj

The idea is to use a repeatable PRNG seed if you want the same deck. Rather than trying to keep a deck in memory, all you need is a seed value so the PRNG spits out the same sequence. The use of Time::HiRes is just so you can get a random-enough seed to use if you don't want a specific deck.

Of course, you'd want to map the single letters to actual card names to be useful.

Now, before you say "But Quix, rand() sucks…", well, yes it does. But you can easily plug in one of a zillion or so better PRNG functions that accept seed values into there.

Not saying this is a better way to do things either, but maybe it's different enough to give you an idea for not having to keep 140K of data sitting around. :)
20 Sep, 2010, Runter wrote in the 3rd comment:
Votes: 0
Looks like the knuth shuffle. I was using that originally.

One of the reasons I changed over is because its appealing to not shuffle at all. O(1) time.

We can debate if its better to err on the size of trivial extra cpu or trivial extra memory.
20 Sep, 2010, David Haley wrote in the 4th comment:
Votes: 0
Quote
The benifit of this is there is no shuffling process and logging many hand histories of entire decks becomes dramatically easier since an entire deck can be represented by a single number.

You can do this also if you store the random seed. Of course, you lose some properties this way that might or might not be interesting to you. It depends on what exactly you're doing.

Note that if you store only the seed, you still get to save on individual representations in the same manner (all you need is the initial seed and the number of cards drawn).

Whether you care about speed or memory depends on what exactly your application is here, how often you shuffle, etc.

Quote
Also this approach guarentees a perfect distribution in shuffling.

Well, it's not the only solution that guarantees a fair shuffle, so this particular property is not a distinguishing factor.
20 Sep, 2010, Scandum wrote in the 5th comment:
Votes: 0
With a 52 card deck there are trillions of possible combinations, so at 52 bytes per deck, 140K would only give you 1500 random decks or something. Loading 1500 saved decks from disk on startup is probably about as fast as randomly generating them, and if less than a thousand games are played each reboot you're probably wasting both cpu and memory.
20 Sep, 2010, KaVir wrote in the 6th comment:
Votes: 0
The solution I used was to create a DeckShuffle() function that iterates through the deck one card at a time, switching each undrawn card for another undrawn card selected at random. I call DeckShuffle() three times at the start of a game, although I'm not sure that's really necessary.

It was just the first solution that sprung to mind, it was easy to implement, and after extensive use it seems to work fine. No doubt there are better solutions, but even if I changed it I doubt the players would notice the difference.
20 Sep, 2010, Runter wrote in the 7th comment:
Votes: 0
Yes. I was hasty in my calculations. There are far too many permutations to make my idea useful.

Ill probably go back to the knuth shuffle.
20 Sep, 2010, David Haley wrote in the 8th comment:
Votes: 0
You might want to reconsider the random seed approach that I mentioned; it lets you keep many of the benefits you had with your list-of-decks idea.

I had assumed that for some reason you were only interested in a subset of possible shuffles. There are 52! possible shuffles for a deck (52 choices for the first card, 51 for the second, 50 for the third…). Scandum has in fact drastically understated the number of shuffles; 52! is about 8 * 10^67, whereas a trillion is "only" 10^12.
I was thinking that maybe for your game, colors didn't matter, or different cards were the same as far as the game rules are concerned, etc., both of which would reduce the number of possibilities considerably.
20 Sep, 2010, Scandum wrote in the 9th comment:
Votes: 0
KaVir said:
The solution I used was to create a DeckShuffle() function that iterates through the deck one card at a time, switching each undrawn card for another undrawn card selected at random. I call DeckShuffle() three times at the start of a game, although I'm not sure that's really necessary.

Sounds like the most efficient solutions to me, as far as I can tell one shuffle should suffice?
21 Sep, 2010, Runter wrote in the 10th comment:
Votes: 0
class Array
def shuffle
length.times do |i|
rng = rand(length-i) +i
self[i] ^= self[rng]
self[rng] ^= self[i]
self[i] ^= self[rng]
end
end
end

deck = (1..52).to_a
puts deck
deck.shuffle
puts deck
21 Sep, 2010, Chris Bailey wrote in the 11th comment:
Votes: 0
def shuffle(set)
(size=set.length).times do |i|
y = rand(size)
set[i], set[y] = set[y], set[i]
end
end


# Can't figure out a good way to make this a one liner =(
def shuffle2(set)
size=set.length.times {|i| set[i], set[y=rand(size)] = set[y], set[i]}
end
21 Sep, 2010, Tyche wrote in the 12th comment:
Votes: 0
I thought Array already had shuffle and shuffle! methods.

So this one-liner works.
>ruby -e 'deck = (1..52).to_a; p deck; p deck.shuffle!; p deck.shuffle!'

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35,
36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52]
[39, 13, 21, 37, 8, 31, 35, 5, 30, 17, 19, 34, 36, 1, 20, 43, 14, 44, 48, 18, 27, 24, 42, 4, 33, 46, 49, 45, 25, 47, 22, 3, 38, 52,
16, 28, 41, 51, 2, 9, 32, 11, 40, 10, 6, 26, 7, 23, 12, 29, 50, 15]
[17, 23, 18, 16, 6, 50, 27, 52, 35, 5, 11, 32, 9, 41, 15, 20, 22, 12, 28, 47, 34, 4, 40, 1, 45, 51, 44, 25, 10, 2, 38, 29, 7, 3, 30,
39, 42, 43, 13, 37, 36, 48, 19, 8, 49, 21, 24, 31, 33, 14, 26, 46]
21 Sep, 2010, Tyche wrote in the 13th comment:
Votes: 0
And using C++ STL…
$ cat deck_shuffle.cpp 
#include <vector>
#include <iterator>
#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
vector<int> deck;
for (int i = 1; i < 53; i++)
deck.push_back(i);
for (vector<int>::iterator i = deck.begin(); i != deck.end(); i++)
cout << *i << " ";
cout << endl;
random_shuffle(deck.begin(), deck.end());
for (vector<int>::iterator i = deck.begin(); i != deck.end(); i++)
cout << *i << " ";
cout << endl;
random_shuffle(deck.begin(), deck.end());
for (vector<int>::iterator i = deck.begin(); i != deck.end(); i++)
cout << *i << " ";
cout << endl;
return 0;
}

$ g++ deck_shuffle.cpp & ./a
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52
46 16 29 41 26 21 20 37 22 32 3 14 30 23 13 52 7 6 18 28 19 34 31 24 9 8 42 27 51 17 40 4 39 11 49 35 12 2 38 25 15 44 36 47 43 45 10 50 33 1 5 48
49 2 19 32 42 5 17 8 22 47 43 26 15 1 16 24 6 38 33 48 39 46 31 12 9 37 20 18 4 30 28 7 25 34 36 41 10 11 27 3 29 44 52 23 45 40 51 35 14 21 13 50
21 Sep, 2010, Chris Bailey wrote in the 14th comment:
Votes: 0
Ah, I didn't know those methods for Array. Thanks Tyche =)
22 Sep, 2010, Runter wrote in the 15th comment:
Votes: 0
Ill have to investigate the built in shuffle.

I think its important when shuffling a deck that all permutations are equally likely. In your examples, chris, all permutations are not equally likely.

http://20bits.com/articles/interview-que...

By following long established algorithms we solve the issue.
22 Sep, 2010, Tyche wrote in the 16th comment:
Votes: 0
Ruby uses Knuth-Fisher-Yates.
long i = RARRAY_LEN(ary);
ptr = RARRAY_PTR(ary);
while (i) {
long j = (long)(rb_genrand_real()*i);
VALUE tmp = ptr[–i];
ptr[i] = ptr[j];
ptr[j] = tmp;
}
22 Sep, 2010, Runter wrote in the 17th comment:
Votes: 0
Then that's likely a great builtin solution for ruby users.
22 Sep, 2010, Chris Bailey wrote in the 18th comment:
Votes: 0
Doh. Well, I won't be making that mistake again! Thanks Runter =)
22 Sep, 2010, David Haley wrote in the 19th comment:
Votes: 0
It's kind of lame that shuffle and shuffle! don't appear in the Ruby documentation for Array… :thinking:
22 Sep, 2010, Runter wrote in the 20th comment:
Votes: 0
I was puzzled by that as well. I suspect it may not be available in all implementations of ruby.
0.0/24