Is this a sufficient way to shuffle a deck of cards?

Question

I am trying to shuffle a deck of cards in my app and I use the following code. Will this sufficiently randomize the deck? I am almost certain is will just want another opinion. Thanks!

for (int i = 0; i < 40000; i++) {
    int randomInt1 = arc4random() % [deck.cards count];
    int randomInt2 = arc4random() % [deck.cards count];
    [deck.cards exchangeObjectAtIndex:randomInt1 withObjectAtIndex:randomInt2];

EDIT: In case anyone is wondering or should come across this in the future. This is what I have gone with to shuffle my deck of cards, it is an implementation of the Fisher-Yates Algorithm. I got it from the post @MartinR suggested below which can be found here: What's the Best Way to Shuffle an NSMutableArray?

NSUInteger count = [deck.cards count];
    for (uint i = 0; i < count; ++i)
    {
        // Select a random element between i and end of array to swap with.
        int nElements = count - i;
        int n = arc4random_uniform(nElements) + i;
        [deck.cards exchangeObjectAtIndex:i withObjectAtIndex:n];
    }

See http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle — Matt, Apr 30 '14 at 16:39
Two improvements - 1) Store `[deck.cards count]` in a variable before the loop so you don't need to call that method 80,000 times. 2) Use `arc4random_uniform(count)` instead of `arc4random` with modulus. — rmaddy, Apr 30 '14 at 16:42
*"Will this sufficiently randomize the deck?"* is more a mathematical question for an expert in probability theory. - An implementation of the Fisher-Yates algorithm for NSArray can for example be found here: [What's the Best Way to Shuffle an NSMutableArray?](http://stackoverflow.com/questions/56648/whats-the-best-way-to-shuffle-an-nsmutablearray). — Martin R, Apr 30 '14 at 16:50
@Rob I meant that `[deck.cards count]` should be stored in a variable before the loop and then in the loop, the variable should be used. This saves 80,000 method calls. — rmaddy, Apr 30 '14 at 17:09
@rmaddy Ah, I misunderstood your point. You're quite right that he can avoid redundant method calls. I was focusing on the more egregious problem is that he's doing anything 40,000 times, when, with the right algorithm, `[deck.card count]` iterations will do the job perfectly. — Rob, Apr 30 '14 at 17:26
@Rob, Yes, reducing the loop from 40,000 to 52 is a much better improvement. :) — rmaddy, Apr 30 '14 at 17:30
Hi Guys, after looking at everything I think I'm just going to go with the Fisher-Yates algorithm. Looks like it does the trick quite nicely! Thanks for all the help. Here is the code I used in case anyone is wondering. int jj = 0; for (int i = [deck.cards count]; i >= 1; i--) { jj = arc4random() % i; [deck.cards exchangeObjectAtIndex:jj withObjectAtIndex:i-1]; } — mattman88, Apr 30 '14 at 18:10

Avt · Accepted Answer · 2014-04-30T16:56:38.110

7

Your code should work rather good if [deck.cards count] < 40000 but following is better

for (int i = [deck.cards count] - 1; i > 0 ; i--) {
    int randomInt1 = arc4random_uniform(i + 1);
    [deck.cards exchangeObjectAtIndex:randomInt1 withObjectAtIndex:i];
}

from docs:

arc4random_uniform() will return a uniformly distributed random number less than upper_bound. arc4random_uniform() is recommended over constructions like ``arc4random() % upper_bound'' as it avoids "modulo bias" when the upper bound is not a power of two.

edited Apr 30 '14 at 16:56

answered Apr 30 '14 at 16:46

Avt

16,927
4
52
72

Why did you change it from counting forwards to backwards? – Guy Kogus Apr 30 '14 at 16:50
@GuyKogus to use 'arc4random_uniform' without additional calculations. – Avt Apr 30 '14 at 16:55
This is not a correct implementation. Please see my answer. – Guy Kogus Apr 30 '14 at 16:56
1

This is still not right. As `i` gets closer to 0 the range of items with which you're swapping objects becomes smaller. The randomisation is meant to go over the entire size of the array. Change `i + 1` to `[deck.cards count]` and you'll hit the spot. – Guy Kogus Apr 30 '14 at 16:59
@GuyKogus It does not matter here. For example first element has possibilities to change its location 'count' times and take any place. So as i gets closer to 0 elements on first positions are most likely already exchanged with some others. – Avt Apr 30 '14 at 17:01
@GuyKogus This is a correct implementation of the [modern algorithm](http://en.wikipedia.org/wiki/Fisher–Yates_shuffle#The_modern_algorithm) of Fisher-Yates shuffle. – Rob Apr 30 '14 at 17:40
Indeed it is! My mistake. – Guy Kogus May 01 '14 at 10:47

Guy Kogus · Answer 2 · 2014-05-01T10:47:07.837

3

Here is the Fisher-Yates algorithm properly implemented. And yes, it will sufficiently randomise your array, I've used it many times and it's just wonderful!

NSUInteger count = [deck.cards count];
if (count > 0) {
    for (NSUInteger i = count - 1; i > 0 ; --i) {
        [deck.cards exchangeObjectAtIndex:i
                        withObjectAtIndex:arc4random_uniform(i + 1)];
    }
}

edited May 01 '14 at 10:47

answered Apr 30 '14 at 16:56

Guy Kogus

7,251
1
27
32

On re-reading the FY algorithm details I realise that this isn't the same. But it still works very well, so whatever. – Guy Kogus Apr 30 '14 at 17:07
4

Shuffling this way actually has a subtle problem so I wouldn't say "it still works very well". See: [The Danger of Naïveté](http://blog.codinghorror.com/the-danger-of-naivete/). A correct FY shuffle avoids this. – Blastfurnace Apr 30 '14 at 17:57
3

Your suggestion to always swap with an index across the whole range actually introduces a observable bias. See the [implementation errors](http://en.wikipedia.org/wiki/Fisher–Yates_shuffle#Implementation_errors) section on the Fisher-Yates page which that, "always selecting j from the entire range of valid array indices on every iteration also produces a result which is biased, albeit less obviously so." I monte-carlo'd both Avt's answer and yours, and the bias introduced by yours was non-trivial (though I'm not sure if you'd notice if you were sitting there, watching the app deal cards). – Rob Apr 30 '14 at 18:02
@GuyKogus Thanks, I have decided to go this route! – mattman88 Apr 30 '14 at 18:28
1

@user3361608: I think that's hilarious. – Blastfurnace Apr 30 '14 at 19:59
@Blastfurnace dang, why is this so complicated, you'd think a clear cut answer would be available online just for shuffling cards – mattman88 Apr 30 '14 at 20:16
1

@user3361608: I know but this code is subtly broken and fixing it to be a _correct_ Fisher-Yates shuffle is so easy. This code looks simple and it "feels right" but that's why it's so pernicious. I trust you'll do the right thing. – Blastfurnace Apr 30 '14 at 20:20
@Blastfurnace after looking at the Fisher-Yates wiki page again I guess the right way to go is to constrain thewithObjectAtIndex:arc4random_uniform(count) from n -> 1 as you go through the iteration. is that what you mean? – mattman88 Apr 30 '14 at 20:25
2

@user3361608: You could implement it yourself based on the wiki page or there are [related question/answers right here on SO](http://stackoverflow.com/questions/56648/whats-the-best-way-to-shuffle-an-nsmutablearray) or Avt's answer above that may help. – Blastfurnace Apr 30 '14 at 20:29
@Blastfurnace great that's actually what I meant! Thanks for your help. – mattman88 Apr 30 '14 at 20:34
1

You guys are amazing! Thank you for teaching me this. I'm updating the answer. – Guy Kogus May 01 '14 at 10:42

score 0 · Answer 3 · answered Oct 25 '18 at 14:27

Depending on how you have implemented your deck you can use simply use Collections.sort() or you can use an ArrayList assuming your implementation is similar to the following

    ArrayList<Integer> originalDeck = new ArrayList<Integer>();
    ArrayList<Integer> randomDeck = new ArrayList<Integer>();

    //Initalize array
    for (int i = 0; i < 52; i++) {
        originalDeck.add(i, i);
    }

    //Smart Implementation
    Collections.shuffle(originalDeck);

    Collections.sort(originalDeck);

    //Long Implementation
    int i=0, max = 0;
    while (originalDeck.size() != 0) {
        max = originalDeck.size();
        i = (int) (Math.random() * max); // goes from 0 to size-1 so always in bounds
        randomDeck.add(originalDeck.remove(i));
    }

Is this a sufficient way to shuffle a deck of cards?

3 Answers3

Linked