How do you shuffle a non-standard deck of cards?

Question

I am making a program to play a game of UNO. In the UNO deck, some cards are repeated, and therefore I cannot just make a list of integers; I have to use objects. I plan on using a LinkedList for the deck, but I am aware that shuffles on a LinkedList are horridly slow.

My question is, should I....

Avoid a LinkedList entirely and just go with an ArrayList
Use an ArrayList or similar, shuffle, then put the contents into the LinkedList
Construct an ArrayList, then make my own shuffling routine (aka not using Random) that adds to the LinkedList as we go
Shuffle the LinkedList anyway (as in, it's not really that bad)

This is not for homework; it is to assist in having fun :)

Why would you want to use a LinkedList for a deck of cards? Why not just use the ArrayList as the deck? — raphaëλ, May 19 '12 at 16:04
Because you need to draw the first card, and add cards to the bottom. LinkedLists are cool for that. — Gyscos, May 19 '12 at 16:05
I would avoid a linkedlist completely. using get/set first/last is np with any other data type as well. And since you need to shuffle, a linkedlist only fits one requirement — keyser, May 19 '12 at 16:05
You can use array-based circular lists that allow you to add to top and bottom, allowing you to get the benefits of using the array without the downsides. But when in Uno do you need to add cards to the bottom? — corsiKa, May 19 '12 at 16:08
I just shuffled a linked list and an array list, the linked list took 42 ms, the array list took 27 ms (this is with 200000 element in them each). With a single or double deck of cards they both showed 0ms. — raphaëλ, May 19 '12 at 16:14
You might want to read this article by Jeff Atwood : http://www.codinghorror.com/blog/2007/12/shuffling.html — Kazekage Gaara, May 19 '12 at 16:18
@KazekageGaara Okay, I'll be sure to use the enviroment's previously-used Random :) — Riking, May 19 '12 at 16:27

score 2 · Accepted Answer · answered May 19 '12 at 16:11

You can represent cards by plain integers. If an integer represents a type of card, and Uno has multiple cards of the same type, just use the integer corresponding to that card more than once.

Shuffling and dealing is easy.

To start the game, set up a fixed size, dumb array of type integer (no fancy linked lists or Arraylist need apply) that can hold the entire deck (size = N). Fill this array with the integers representing the Uno deck including the duplicate integers representing duplicate cards. Set UNDEALT to N.

To shuffle, execute the following code some modest (100?) times:

 1)  Pick a random number from 1 to UNDEALT, R.
 2)  Exchange the the first array slot with the Rth slot.

To deal:

 1) Give out the card in the UNDEALT slot.
 2) Decrement UNDEALT.

You can do all this with fancier data structures, too, but there just isn't any point. Given that the total information involved is 100 data items, unless you do something outrageously dumb, it'll be faster than people. But my motto is: if simple works, stick with simple.

score 2 · Answer 2 · edited May 23 '17 at 10:34

A few thoughts:

There is no reason to stick with a LinkedList for this; you can just as easily use an ArrayList to get the first and last cards. In fact, it appears that ArrayList's performance is better for removing single elements.
You may also shuffle an array of elements which have identical integers. As in, there is no reason that you cannot use a shuffling algorithm with an array that looks like this:

cards[] = {1, 1, 1, 1, 2, 3, 4, 5, 6, 6}, where 1 = "Wild", 2 = "Draw Four", or what have you.

In my opinion, using an Array(List) would make it easiest to do so. The difference here is using the array's values for gameplay, rather than their keys to determine what the card is.

You can do the same thing with objects if you'd like; you shuffle the array based on array index, but use the values in the array (objects representing cards) to know what the card actually is.

edit: Apparently Java will shuffle things for you! http://docs.oracle.com/javase/6/docs/api/java/util/Collections.html#shuffle(java.util.List)

We're not talking about arbitrary removals; only removals from the top of the list. Also, your last two paragraphs are confusing and just repeating things that should be fairly obivous. — Riking, May 19 '12 at 16:21

score 0 · Answer 3 · answered May 19 '12 at 16:04

0

If you don't shuffle too often, it won't be that slow.

One way to shuffle is to randomly permute the first card with another one. This isn't that slow with a LinkedList. Copying it to/from an ArrayList, on the other hand, is going to take some time.

answered May 19 '12 at 16:04

Gyscos

1,772
17
22

1

Dumping to an array, sorting, and dumping back to linked list is MUCH faster than sorting with linked list. So much so that the default implementation in `java.util.Collections.sort(List)` dumps to an array to sort. – corsiKa May 19 '12 at 16:09
Not dumping to arrays by avoiding the need to copy the data is even faster. "permute first card with another" I agree is the right "shuffle" step, but doing an exchance of two slots in a fixed size array is less code and faster than messing with linked lists. And you're likely to even code it right on the first try. – Ira Baxter May 19 '12 at 16:16

How do you shuffle a non-standard deck of cards?

3 Answers3