"shuffling cards" algorithim

[CaptainPinko]

I am building a game and need to shuffle a deck of cards and am trying to be creative on my own (it's more of challenge and better learning experience to come up with a good solution than to read the perfect solution). So I came up with this algorithim/approach. I'm looking for criticism.

1) Create a wrapper for your objects that are to be 'shuffled' that consist of an 'index' and a pointer.

class ShuffleSlot {
private int index;
private Object obj;
ShuffleSlot (Object obj, int idex){
this.obj = obj;
this.index = index;
}
int getIndex () {return this.index;}
}


2) Now as you iterate through your collection of elements drop each one into a wrapper and assign it a random number from lets say 0 to 10 or 100 times your collection size and add the wrapper into a binary tree* sorted by their random index number. (I mentioned making the index range larger than the sample to prevent collisions since most binary-trees are made as in-order sorts so having collisions would preserve some of the order.)

3) Do a traversal on your tree (shouldn't matter what kind) and there you have a random ordering.

4) If in practice this is not random enough then you could repeat the process a certain number of times proportional to the sample size. (say 1/5).

Benefits:
+ even if you don't know size of the sample it won't break (like overflow).
+ most languages provide binary-trees for you as part of standard libraries.
+ order on insertion is log n so it seems like it would be effecient

Criticisms:
- floating point is slow
- binary trees eat up memory

*not sure if an AVL tree is a benefit here... it will have faster insertions but since we aren't searching thats no help against the overhead and i don't think the shape of the tree affects the traversal time.

[IsaacKuo]

I have used this sort of shuffling scheme with databases because it's the laziest way to do it--I just use one SELECT to create a table with the record keys and random numbers, and then another SELECT with order set to the random number field. It's not the most efficient use of computing resources, but it's easily the most efficient use of programmer resources.

But if I were shuffling stuff in a more traditional programming language, I'd just use your basic "random card swap" method. You start with a deck of cards, and do the following:

for i=1...sizeofdeck
pick j randomly between 1 and i-1 (inclusive)
swap card[i] with card[j]
endfor

You don't actually need to know the size of the deck a priori, but you do need to know when you're at the end of the deck. ;)

[CaptainPinko]

for i=1...sizeofdeck
pick j randomly between 1 and i-1 (inclusive)
swap card[i] with card[j]
endfor

You don't actually need to know the size of the deck a priori, but you do need to know when you're at the end of the deck. ;)

Hmm, would work for arrays and anything else indexable (e.g. Vectors) but that wouldn't work with streams. Requires no extra memory and is order n. Nice. It's so simple why didn't I think of that?

I wonder if there is any meaningful way to quantify the randomness of a shuffle.

Yeah, I really was pulling a Rube Goldberg back there... lol with an answer so simple (and ovbious :o ) no wonder I didn't find anything on the 'net. *tsk tsk*