CODEWITHSUNDEEP
javaarraysobjectruntimeshuffle
Only_Maxi
Only_Maxi

Reputation: 33

Is there an algorithm for shuffling objects in an array randomly WITHOUT utilizing Lists and Collections

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?

Upvotes: 3

Views: 63

Answers (2)

Marce Puente
Marce Puente

Reputation: 397

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.

Upvotes: 1

Sash Sinha
Sash Sinha

Reputation: 22360

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

Upvotes: 7

Related Questions