3

I want to shuffle an array of Objects in a card game simulation.

I scrolled through many posts on here and almost all of them mention transforming the array into a list, then shuffling it using an implementation of Collections.shuffle() and then transforming it back into an array.

However, since I actually want to understand what is going on while the shuffling is happening, I want to implement it myself. I wrote this code for my array of Card objects in the array unshuffledDeck[]:

Random shuffleRandom = new Random();
Card[] shuffledDeck = new Card[cardAmount];
for (int i = 0; i < cardAmount; i++) {
    int j = (int) (shuffleRandom.nextFloat() * cardAmount);
    shuffledDeck[i] = unshuffledDeck[j];
}

However, depending on the random number, multiple entries in the shuffledDeck output array can have the same Card in it, which I don't want.

Now I have thought about just adding an if statement to check if the card is already in one of the other entries, something like

Random shuffleRandom = new Random();
Card[] shuffledDeck = new Card[cardAmount];
for (int i = 0; i < cardAmount; i++) {
    int j = (int) (shuffleRandom.nextFloat() * cardAmount);
    boolean cardIsNotYetPresent = true;
    for (int k = 0; k < cardAmount; k++) {
        if (k != i && shuffledDeck[k] == unshuffledDeck[j]) {
            cardIsNotYetPresent = false;
            break;
        }
    }
    if (cardIsNotYetPresent) {
        shuffledDeck[i] = unshuffledDeck[j];
    } else {
        i--;
    }
}

, but that increase the duration drastically, which is not what I want. How would I approach this problem without adding another O(n) to the runtime of the algorithm?

Improve this question
3
  • 1
    Array is a very inefficient structure for shuffling. Why would you need to use arrays? The algorithms are way too trivial to discuss, but the performance is always too bad, because you would need to move big volumes of memory. Why? Will you consider using something else? Commented Feb 3 at 23:35
  • Seeing as someone else already gave a very good solution for my problem, I'll be implementing that. But to answer your question, I have been using arrays since I learnt about them studying computer science. I know they're not the best solution performance wise but the project I'm working on right now is just a little fun side thing until lectures continue next semester, so I kind of want to try and use only the stuff I already learnt. Should I come back to this project one day though, I'll definitely consider using more advanced features Commented Feb 4 at 11:24
  • 2
    On the contrary, arrays are a good solution to this problem. They actually have better performance than collection classes such as ArrayList (which actually use arrays behind the scenes) or LinkedList (which typically have very poor performance). The main downside is that they're not very versatile in use. Commented Feb 4 at 15:07

2 Answers 2

Reset to default
7

Consider implementing the Fisher–Yates shuffle.

Instead of randomly picking an index and checking for duplicates, it works by iterating through the array from the last element to the first and swapping the current element with a randomly chosen earlier element (including itself). This ensures the time complexity is O(n).

import java.util.Random;

class Card {
    private final String suit;
    private final String rank;

    public Card(String rank, String suit) {
        this.rank = rank;
        this.suit = suit;
    }

    @Override
    public String toString() {
        return rank + " of " + suit;
    }
}

public class CardShuffler {
    public static void fisherYatesShuffle(Card[] deck) {
        Random random = new Random();
        int n = deck.length;
        for (int i = n - 1; i > 0; i--) {
            int j = random.nextInt(i + 1);
            swap(deck, i, j);
        }
    }

    private static void swap(Card[] deck, int i, int j) {
        Card temp = deck[i];
        deck[i] = deck[j];
        deck[j] = temp;
    }
    
    private static void printDeck(Card[] deck) {
        for (Card card : deck) {
            System.out.println(card);
        }
    }

    public static void main(String[] args) {
        String[] suits = {"Hearts", "Diamonds", "Clubs", "Spades"};
        String[] ranks = {"2", "3", "4", "5", "6", "7", "8", "9", "10", "Jack", "Queen", "King", "Ace"};
        Card[] deck = new Card[52];
        int index = 0;
        for (String suit : suits) {
            for (String rank : ranks) {
                deck[index++] = new Card(rank, suit);
            }
        }
        fisherYatesShuffle(deck);
        System.out.println("Shuffled Deck:");
        printDeck(deck);
    }
}

Example Output:

Shuffled Deck:
4 of Clubs
8 of Spades
2 of Diamonds
King of Hearts
3 of Diamonds
3 of Clubs
10 of Clubs
4 of Spades
10 of Hearts
Queen of Spades
6 of Hearts
8 of Diamonds
Jack of Spades
King of Spades
5 of Spades
Queen of Diamonds
3 of Hearts
Queen of Hearts
8 of Hearts
2 of Hearts
10 of Spades
2 of Clubs
Jack of Clubs
Ace of Hearts
5 of Hearts
King of Diamonds
10 of Diamonds
5 of Diamonds
7 of Clubs
9 of Clubs
5 of Clubs
6 of Spades
6 of Clubs
9 of Spades
9 of Diamonds
Jack of Hearts
2 of Spades
7 of Hearts
4 of Diamonds
King of Clubs
9 of Hearts
Ace of Diamonds
Ace of Clubs
7 of Diamonds
4 of Hearts
Ace of Spades
8 of Clubs
Queen of Clubs
Jack of Diamonds
3 of Spades
6 of Diamonds
7 of Spades

Try on JDoddle

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Thank you very much, this helped a lot! I understand it now and an adapted and applied version of the shuffler now works in my project!
1

I know you don't want to use lists or collections, but I think any other way is ostensibly more onerous.

public class Deck {

   private void ini() {
      create();
      shuffle();
   }
   
    List<Card> deckOfSortedCards = new ArrayList<>();
    Card deckOfUnorderedCards[] = new Card[ 52 ];
    
      // we create the initial "deck"
    void create() {
       for( int i = 0; i < 4; i++ ) {
          for( int k = 0; k < 13; k++ ) {
             deckOfSortedCards.add( new Card( i, k ));
          }
       }
    }
    
      // we fill the deck with the disordered cards
    void shuffle() {
       Random ran = new Random();
       for( int i = 0; i < 52; i++ ) {
            // it is probably better to use a copy of “deckOfSortedCards”, 
            // to avoid having to create it for each new “hand”.
          deckOfUnorderedCards[ i ] = deckOfSortedCards.remove( ran.nextInt( 0, deckOfSortedCards.size() ) );
       }
       System.out.println( Arrays.toString( deckOfUnorderedCards ) );
    }

   class Card {
      int suit, value;
      String name;
      
      Card( int sui, int val ) {
         suit = sui;
         value = val;
         String aux = "";
         if( value < 10 ) aux = "" + ( value + 1 );
         if( value == 10 ) aux = "Jack";
         if( value == 11 ) aux = "Queen";
         if( value == 12 ) aux = "King";
         switch( sui ) {
            case 0: name = aux + " of the Spades"; break;
            case 1: name = aux + " of the Hearts"; break;
            case 2: name = aux + " of the Diamonds"; break;
            case 3: name = aux + " of the Clubs";
         }
      }
      
      @Override
      public String toString() {
         return name;
      }
   }

   public static void main( String[] args ) {
      new Deck().ini();
   }
}

It is understood that the environment I have created is only one of the possible ways to choose.

Improve this answer

1 Comment

As i mentioned in another comment, I wanted to use Arrays as I only learnt about them so far and in our lecture lists haven't been discussed yet. However, someone else has posted a suitable solution for me and that solved my problem. Still, thanks for answering!

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.