java - Is there an algorithm for shuffling objects in an array randomly WITHOUT utilizing Lists and Collections - Stack Overflow

admin管理员组

文章数量:1304843

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?

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?

• java
• arrays
• object
• runtime
• shuffle

Share Improve this question Follow asked Feb 3 at 23:20 Only_MaxiOnly_Maxi 3333 bronze badges 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? – Sergey A Kryukov 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 – Only_Maxi 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. – k314159 Commented Feb 4 at 15:07

Add a comment  | 

2 Answers 2

Sorted by: 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

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.

本文标签：