Creating an array of random numbers with no duplicates

Question

I only need three random numbers within the range of 1-54 (deck of cards) and none of the three numbers can be a duplicate. I cannot use an ArrayList; I must use a standard array. Is the method I chose to check for duplicates good enough?

public class Test {

public static int genRandom() {
    // generate random int value between 1 and 54
    int random = 1 + (int) (Math.random() * ((54 - 1) + 1));
    return random;
}

public static boolean containsDuplicates(int[] arr) {
    // check to see if positions have matching values
    if (arr[0] == arr[1] || arr[0] == arr[2] || arr[1] == arr[2]) {
        System.out.println("Duplicates Exist");
        // if matching value is found, randomize the array again
        shuffle(arr);
        return true;
    }
    System.out.println("No duplicates");
    return false;
}

public static void shuffle(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        arr[i] = genRandom();
        System.out.println(arr[i]);
    }
    containsDuplicates(arr);
}

public static void main(String[] args) {

    int[] cards = new int[3];
    shuffle(cards);
}
}

Answer 1

No, not a good way at all.

shuffle and containsDuplicate recursively call each other without guarantee to ever stop doing that. That is the program has a certain probability to die because of stack overflow.

A similar non-recursive version

    public static boolean containsDuplicates(int[] arr) {
        return arr[0] == arr[1] || arr[0] == arr[2] || arr[1] == arr[2];
    }

    public static void shuffle(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            arr[i] = genRandom();
        }
    }

    public static void main(String[] args) {
        do {
            shuffle();
        } while(containsDuplicates());
    }

doesn't suffer stack overflow, but still may run for indefinitely long time.

As Jerry Coffin mentioned in the comment, a Fisher-Yates algorithm is a way to go.

Answer 2

Don't use Math.random to generate random numbers. It's obsolete, error prone, and really insane bugs can happen. The modern way is to create an instance of Random, and call its appropriate methods. In this example nextInt.

Although @vnp's solution eliminates the risk of stack overflow, theoretically speaking it doesn't guarantee termination.

Here's a straightforward algorithm to generate 3 distinct random numbers out of 54:

• Create an array of 54 elements, with the desired values (1 to 54)
• Get a random number x between 0 and 53 (inclusive), and swap the elements in the array at position x and 53 (the last element)
• Get another random number x, but this time between 0 and 52 (inclusive), and swap the elements in the array at position x and 52
• Get another random number x, but this time between 0 and 51 (inclusive), and swap the elements in the array at position x and 51

And that's it. The last 3 elements of the array are distinct random elements.

Something like this:

class Deck {
    private static final int SIZE = 54;
    private final Random random;

    public Deck(Random random) {
        this.random = random;
    }

    public int[] drawRandomCards(int count) {
        int[] cards = newFullDeck();
        shuffleLastN(cards, count);
        return Arrays.copyOfRange(cards, cards.length - count, cards.length);
    }

    private void shuffleLastN(int[] cards, int count) {
        assert count < cards.length;

        for (int i = 0; i < count; ++i) {
            int k = random.nextInt(cards.length - count);
            swap(cards, cards.length - 1 - i, k);
        }
    }

    private void swap(int[] cards, int i, int j) {
        int tmp = cards[i];
        cards[i] = cards[j];
        cards[j] = tmp;
    }

    private int[] newFullDeck() {
        int[] cards = new int[SIZE];
        for (int i = 0; i < cards.length; ++i) {
            cards[i] = i + 1;
        }
        return cards;
    }
}

Answer 3

Just use a Set: Set<Integer> set = new Hashset<>();

It handles all of the duplicate removal automatically.

Answer 4

the most efficient way would be to implement "the random playlist algorithm" https://stackoverflow.com/questions/5467174/how-to-implement-a-repeating-shuffle-thats-random-but-not-too-random, it is basic simple well know algorithm.

***some one already gave this answer - "Fisher–Yates shuffle"

It seems like the most obvious way would be to start with an array[54] containing 1..54, then shuffle that, and keep the first three values in it.

no need to shuffle all the array, just the first three items..

Answer 5

Java 8 solution with streams:

int[] cards = ThreadLocalRandom.current().ints(1, 55).distinct().limit(3).toArray();

• Uses the current ThreadLocalRandom to create a stream of random int values in the range 1..54
• Lets only distinct values pass
• Terminates after 3 distinct values have been found

Answer 6

As Janos and a couple of other people have already mentioned, the easiest way to draw three random cards fairly (without putting any back in the deck) is to do what effectively amounts to three steps of a Fisher-Yates shuffle. Janos' explanation is doubtless the best.

However, it should be noted that a random generator needs some horsepower in order to drive a 54-card deck. It needs to have at least ceil(log(54!)/log(2)) bits of state - about 238 - to be able to (potentially) generate every possible permutation of 54 cards.

Some current language runtimes have generators that meet this requirement but none - not Java, not .Net, not C++ - ship with any decent generators that fulfil basic quality criteria for pseudorandom number generators (PRNGs). Yes, even the mighty mt19937 Mersenne generator with its astronomical period fails certain basic tests. I doubt that so many people would still like it if they knew what a prissy beast it is and all the caveats that govern its proper use.

The random generators that ship with current language runtimes aren't good for much except for homework assignments and for light testing duty.

There's one additional caveat that concerns drawing unbiased random numbers in some given range, as when following Janos' description how to draw three cards fairly.

For example, if a generator is available that returns random 32-bit numbers - like Java's Random.nextInt() - then one might be tempted to use modulo division in order to get a random number in some reduced range. Now take this example (unsigned for the sake of exposition):

random_uint32() % 0xAAAAAAAAu

It will indeed yield values in the half-open range [0, 0xAAAAAAAAu) but all values in the first half of the range are exactly twice as likely as those in the second half. Why? The period of the generator is not an exact multiple of the modulus, and so some results must occur more often than others. That's called bias. Just as problematic is multiplying a random float in the range [0.0, 1.0) with the modulus:

random_double() * modulus

It suffers from exactly the same problem, except that the excess isn't dumped at the beginning of the range as in the earlier example. Instead the difference is smeared over the whole range, so that more likely results are mixed with less likely ones in a regular pattern.

One standard way of eliminating bias in this situation is to use the rejection method. It can be used to achieve unbiassed results of virtually any size or shape from a uniform random source. In the case under consideration it works by keeping only such random numbers that fall in the range [0, floor(R / modulus) * modulus) where R is the period of the random generator (2^32 in the earlier example). The other numbers are thrown away and a new one is drawn. The result is that a subsequent modulo division with the modulus leaves a perfectly unbiassed result.

Java's Random.nextInt(int) employs exactly this method (see source code), so all is well.

However, its twin method in the .Net framework - Random.Next(Int32) - cuts corners by using the multiplication method above, after needlessly converting the random bits to a double. So it has not only poor quality, but also poor performance to boot. The full scale of the disaster can be inspected in the published source code.

In other words, just because something is a basic part of a modern/recent language runtime or standard library doesn't mean it has to be any good. And something that works perfectly well in one Javaish/Hashish language may not work quite so well in the other (C# isn't always the black sheep here), even though the statements look virtually identical and the classes even have the same names. Caveat emptor.

Note: the problems I mentioned will not cause mission failure in a homework assignment but it would be wise to keep them in mind whenever the topic veers towards computers, gambling and fair dice... It's not hard to build (or find) a decent random generator for whatever one's requirements might be; however, saying new Random() works only for the lightest of duties.