Checking an integer in an array

Question

I have an exercise in college, part of which consists of creating a pack of cards that must then be shuffled. I have cards in the array (not shuffled) and you want to shuffle them and push on the home stack, from which I can pull cards to deal with them.

My problem is that I want to check that the random number that I generate (and which represents one of the cards in the array) is not yet on the stack. From reading on this forum, I came up with code that I think should work. When debugging, I notice duplicates.

According to my comment below we cannot use the Collections structure (edit)

private Stack<Card> deck;//to hold cards private Card[] protoDeck;//to hold cards before shuffling private Random randomer; private int cardsDealt;//how many cards used. Used for other methods private static final int TOTALCARDS = 52;//sets limit of deck for all decks public void shuffle(){//remove cards from deck and put back in random order randomer = new Random(); int[] temp = new int[TOTALCARDS];//to keep track of random numbers int rand = 0; for (int i = 0; i < temp.length ; i++) { do {//keep creating randoms if rand = randomer.nextInt(TOTALCARDS); deck.push(protoDeck[rand]);//puts the Card onto the Deck in a random position temp[i] = rand; } while (!(Arrays.asList(temp).contains(rand)));//check if the number already used } } 

---

@PeterLawrey I changed the code a bit, since I just need to shuffle the full decks, and it works, I will lay out the cards from the stack to deal with

---

 public void shuffle() { randomer = new Random(); for(int i = 0; i < TOTALCARDS; i++) { // pick a random card from the rest of the deck int j = randomer.nextInt(protoDeck.length - i) + i; // swap cards Card tmp = protoDeck[i]; protoDeck[i] = protoDeck[j]; protoDeck[j] = tmp; deck.push(protoDeck[i]); } } 

Thanks to Peter and all the other participants. M.

Answer 1

Beginning with

 private final Card[] deck;//to hold cards before shuffling private final Random rand = new Random(); 

You can do

 public void shuffle() { // no need the shuffle the last card. shuffle(deck.length - 1); } // will leave the first N card random without duplicates. public void shuffle(int numberOfCards) { for(int i = 0; i < numberOfCards; i++) { // pick a random card from the rest of the deck int j = rand.nextInt(protoDeck.length - i) + i; // swap cards Card tmp = deck[i]; deck[i] = deck[j]; deck[j] = tmp; } } 

Cost O (N), where N is the number of random cards.

---

Imagine you have a small deck, for example

 AS AC AD AH 2S 2C 2D 2H 

and you need to choose a random first card, you select one of the deck and change it. Say nextInt () 5 => 2C

 2C | AC AD AH 2S AS 2D 2H 

The table consists of randomly selected cards + not selected. You do not have duplicates, because the same cards are moving. The following random card, for example, 2H, which is replaced by AC

 2C 2H | AD AH 2S AS 2D AC 

Finally, AD is selected.

 2C 2H AD | AH 2S AS 2D AC 

This gives you three random cards, and the rest. The same array can be used again, since starting with a sorted or random deck does not make the result more or less random.

---

In response to the answer, Why does this simple shuffling algorithm produce biased results? if there are 123, possible results

 123 +- 123 - swap 1 and 1 (these are positions, not numbers) | +- 123 - swap 2 and 2 | +- 132 - swap 2 and 3 +- 213 - swap 1 and 2 | +- 213 - swap 2 and 2 | +- 231 - swap 2 and 3 +- 321 - swap 1 and 3 +- 321 - swap 2 and 2 +- 312 - swap 2 and 3 

As you can see, there are only 6 possible results, all are equally likely.

Answer 2

Actually Stack extends Vector. Thus, you can use the contains method to verify that an element already exists.

Answer 3

The original problem is that Arrays.asList(temp) does not create a List<Integer> , but << 22>.

Therefore, Arrays.asList(temp).contains(rand) always returns false .

If you used the Integer wrapper class ( Integer[] temp = new Integer[TOTALCARDS]; ), that would work, but your approach is very inefficient, since you will have to generate a "random" number in the set, which will decrease at each iteration.

One way is to create an array containing a position from 0 to 51, shuffle it, and then scroll through it to click cards in the deck.

 public void shuffle(){//remove cards from deck and put back in random order int[] temp = new int[TOTALCARDS];//to keep track of random numbers for(int i = 0; i < temp.length; i++){ temp[i] = i; } //shuffle the array for (int i = 0; i < temp.length ; i++) { deck.push(protoDeck[temp[i]]); } } 

This approach works in O (n) time.

Answer 4

I may have misunderstood it, but I think your concept is bad.

• generate random number
• put it in a new deck
• check if he is there

It seems to me that this is the wrong order. On the other hand, using Set always works if you want unique elements.

Answer 5

As pointed out by @ ZouZou , Arrays.asList(temp) returns a List<int[]> . You can do this because of the confusion caused by this answer (which, by the way, is wrong). This answer shows the way you can do this using binary search:

 public boolean contains(final int[] array, final int key) { Arrays.sort(array); return Arrays.binarySearch(array, key) >= 0; } 

Changes the passed array. You will have the opportunity to copy the array and work with the original array ie int[] sorted = array.clone(); But this is just an example of short code. Runtime O(NlogN) .

In the Java documentation, binarySearch will return one of the following values ​​(I highlighted important points):

index of the search key, if it is contained in the list; otherwise (- (entry point) - 1) . The insertion point is defined as the point at which the key would be inserted into the list: the index of the first item is greater than the key or list.size () if all the items in the list are less than the specified key . Note that this ensures that the return value will be> = 0 if and only if the key is found.