What's a good shuffle percentage?

views:

103

answers:

+3 Q:

What's a good shuffle percentage?

Hi,

I'm basically new to coding for random results, but did some reading and tested out the javascript version of the Fisher-Yates algorithm (as seen on wikipedia), with an ordered list.

I ended up adding code to make sure the array was shuffled differently than its initial order, and also calculated the percentage of how many objects were shuffled to a different position by the algorithm.

So I'm wondering what might be considered a good result. Kind of a generic question. If I shuffled a deck of cards, what would be the least acceptable amount of shuffle? Right now I have mine coded to repeat the algorithm if it comes out less than 25 percent shuffled.

What do you think?

+9 A:

Zero. You can make any number of checks you like to make it feel more random, but even the check for the same order makes your algorithm flawed.

Eiko 2010-10-11 04:58:05

+1. All permutations of the deck should be equally probable. Anything else isn't a good shuffle.

JoshD 2010-10-11 05:12:33

One comment: It's very much dependent on your use case if it's a bug (poker, slot machine, ...) or a feature (button labeled "show me different colour scheme for my wall paintings").

Eiko 2010-10-11 05:30:30

Right, its more at the "show me different colour scheme for my wall paintings" scenario. I guess that doesn't come up much.

op1 2010-10-11 05:42:22

Maybe it would be more direct if I coded a non random shuffle that mixed things up more consistently than the random shuffle.

op1 2010-10-11 06:01:00

+6 A:

If your shuffle algorithm is correctly implemented and produces a truly random shuffle (modulo your PRNG's randomness, or lack thereof), I wouldn't reshuffle at all. In particular, the fact that you don't accept random configurations that are 25+% similar to your original configuration tells an adversary that they can expect not to see any of those configurations after your shuffling completes.

ide 2010-10-11 04:58:42

Oh, I'm not actually going to shuffle cards, its really for a list (no strategy involved). There was a big difference between sorting five items and fifteen. The five item sort returned identical lists occasionally, while the fifteen item sort was always between 60 and 90 percent shuffled (to the extent that I checked). I probably won't be sorting massive lists, but would like a significant amount of shuffle without having to repeat the cycle too many times.I didn't actually change the algorithm, I just put conditons on it for practical purposes.

op1 2010-10-11 05:11:47

+1 here, too! :)

JoshD 2010-10-11 05:12:57

With five elements your list should be sorted identically one in 120 shuffles. You really want to check your algorithm works right. Shuffling is *not* a trivial thing, and there are countless things that can go wrong (which just looked so obvious).

Eiko 2010-10-11 05:17:41

// fisher-yates sort example, as seen online...var i,j,tmp;for(i = n - 1; i > 0; i--){ j = Math.floor(Math.random() * (i + 1)); tmp = aA[i]; aA[i] = aA[j]; aA[j] = tmp;}

op1 2010-10-11 05:35:22

I don't know how to format that on this site, but the thing is if I click a button that says "shuffle" and nothing happens (or almost nothing gets sorted), it kind of sucks.

op1 2010-10-11 05:38:20

@op1 If that's your use case, then you are not after a true random shuffle.

Vinko Vrsalovic 2010-10-11 06:11:13

Yeah it must have been all of the talk about randomness associated with shuffling that got me there (now I understand the bogosort).

op1 2010-10-11 06:14:30

Thanks for the feedback. All of your answers were relevant.

I'm adding this answer since my notion of shuffling went from random to non random, and now I'm using a hybrid of the two.

With the perfect in-shuffle I can generate multiple lists in different orders (which modulate off the number of items). However, when the number of items is odd, the last number does not get shuffled. So I decided to randomize its position in the shuffled list.

In the process of figuring that out, I made a table generator which displays all the lists possible given a number of items. It's pretty interesting. For example, the number 52 generates 52 columns, while the number 51 only generates 8 columns.

op1 2010-10-12 09:25:27

By the way, that only works well if the entire cycle of lists is generated while the random position of the odd item is determined for each list in the process. If instead it is done for one shuffle at a time, the random number will throw off the next sequence in the cycle.

op1 2010-10-13 07:09:37

ansaurus

tags:

views:

answers:

What's a good shuffle percentage?

related questions