2
\$\begingroup\$

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);
}
\$\endgroup\$
  • \$\begingroup\$ You're essentially shuffling an array, to which there is a well known good algorithm. Inventing a new one makes sense only if you have other requirements than "producing a shuffled deck." \$\endgroup\$ – TorbenPutkonen Feb 19 at 2:52
1
\$\begingroup\$

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();
  }  
}

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thank you for this incredible response, it's going to take me a bit to get through it all, I will post updates and edits when I finish. I have a lot of school assignments right now and this is apart of a bigger program and now that I understand the purpose of pure functions and "magic numbers" replaced with constants I think I will write far more intuitive programs going forward :) Thank you! \$\endgroup\$ – ErlichBachman Feb 18 at 0:50
  • \$\begingroup\$ Hi, so I was hoping to port my card game application over to the web at some point which is when it seems like a DI pattern would make sense but for my current program I'm not sure it makes sense, maybe you could shed some light on this... \$\endgroup\$ – ErlichBachman Feb 18 at 4:05
2
\$\begingroup\$

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?

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thank you for your response! So shuffle is a behavior in a Deck object that has the field deck which is non-static and private. LOL sorry i = 0 was left over from running some mean/standard deviation/chi-squared tests....... woops..... Maybe you can explain your logic for creating a constant, not that I think its unreasonable. I would argue that it just creates another Attribute that needs to be on the Stack at runtime, obviously in this case doesn't matter but in a bigger program would just mean more memory usage for a variable that doesn't need to be there. \$\endgroup\$ – ErlichBachman Feb 17 at 9:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.