Is this a reasonable algorithm for shuffling cards?

Question

So I based my "algorithm" on the poke method defined by Persi Diaconis. You start with the card at the bottom of a given deck and then poke the top card into a random position in the deck. At first the probability of this happening is 1/52 but once a card is below the bottom most card it increases to 2/52 since there is now two positions a card could go to move the bottom card up the deck.

He claims it takes about 200 of these pokes to get the bottom card to the top. Then you poke the that bottom card which is now at the top somewhere random in the deck and he claims it is now completely randomized.

My results have held true to that, I haven't calculated mean or standard deviation yet to check but just from initial runs it seems to hold true(he is a mathematician and I am a first year undergrad, of course its true).

public void shuffle()
{
    SecureRandom rnd = new SecureRandom();
    Card bottomCard = deck.get(deck.size() - 1);
    int i = 0;
    while(!deck.get(0).equals(bottomCard))
    {
        Card poke = deck.get(0);
        deck.remove(0);
        deck.add(rnd.nextInt(52), poke);
    }
    deck.remove(bottomCard);
    deck.add(rnd.nextInt(52), bottomCard);
}

Answer 1

I assume that shuffle is inside a class that represents a Deck.

---

52 is a magic number. We could simply replace it by a constant variable with the name size:

public final int size = 52;

public void shuffle() {
    /* ... */
    while(/* ... */) {
       /* ... */ 
       deck.add(rnd.nextInt(size), poke);
    }
    /* ... */
    deck.add(rnd.nextInt(size), poke);
}

One important benefit is that we don't have to change 52 at multiple places if the size should change and typos can be avoided too.

---

Card poke = deck.get(0);
deck.remove(0);

This snipped can be simplified:

Card pole = deck.remove(0);

---

Extract SecureRandom to the class scope to only create an instance of it once instead for every shuffle invocation.

If you are interested in testing we should try to make shuffle a pure functions, because they are easy to test. Since we depend on SecureRandom and randomness makes a method impure we need to override the method nextInt to return a constant value and inject it as a dependency:

class Test {
  class MockedRandom extends SecureRandom {

    int number;

    MockedRandom(int number) { this.number = number; }

    @Override
    public int nextInt(int bound) {
      return number;
    }

  }

  @Test
  void example() {
    Deck deck = new Deck(new MockedRandom(5));

    deck.shuffle();

    assertThat(...)
  }


} 

---

A Deck could contain besides suffle methods like drawFromTop, last, remove and addRandomly to make the algorithm more readable:

public void shuffle() {
  while (first().equalsNot(last())) {
    addRandomly(drawFromTop());
  }

  addRandomly(drawFromBottom());
}

---

I do not know which data structure you use for deck but if it is not an LinkedList you should think if the operation deck.add(rnd.nextInt(52), poke); could cause a performance issue for you.

---

class Deck {

  private final SecureRandom rnd = new SecureRandom();
  private final int size = 52;
  private LinkedList<Card> deck;

  public void shuffle() {
    while (first().equalsNot(last())) {
      addRandomly(drawFromTop());
    }

    addRandomly(drawFromBottom());
  }

  /**
   * Adds card at a random position
   *
   * @param card to add
   */
  private void addRandomly(Card card) {
    deck.add(rnd.nextInt(size), card);
  }

  /**
   * shows last card in the deck without to modify it
   */
  public Card last() {
    return deck.getFirst();
  }

  /**
   * shows first card in the deck without to modify it
   */
  public Card first() {
    return deck.getLast();
  }

  /**
   * removes first card from the deck and returns it
   */
  public Card drawFromTop() {
    return deck.removeFirst();
  }

  /**
   * removes last card from the deck and returns it
   */
  public Card drawFromBottom() {
    return deck.removeLast();
  }  
}

---

Answer 2

It's an interesting approach... Some cleanup to consider...

int i = 0;

i is never used...

rnd.nextInt(52)

You might want to interrogate the size of deck at the start of the method, rather than using a fixed 'magic' number. That would mean that you'd be able to use the method to shuffle decks of multiple packs of cards for example...

deck.remove(bottomCard);

Although you're treating this as a unique case, it's still card 0, I'd consider defining a constant FIRST_CARD_IN_DECK=0 to represent the card to remove.

It's unclear where deck comes from should it be passed into the shuffle function?