Check for duplicates while populating an array

Question

I have an array that I populate with 6 randomly generated numbers. First it generates a random number between 1 and 49 and then checks it against the numbers in the array. If it finds a duplicate it should generate a random number again and then perform the check once again. If there are no duplicates then the number is added to the array.

Here's the code:

public void populateArray()
{
    for(int i = 0; i < numberLine.length; i++)
    {
        randomNumber = 1 + randomGen.nextInt(49);
        for(int j = 0; j < i; j++)
        {
            if (numberLine[j] == randomNumber)
            {
                i--;
            }
            else
            {
                continue;
            }
        }
        if(i >= 0)
        {
            numberLine[i] = randomNumber;
        }
        else
        {
            continue;
        }
    }
    Arrays.sort(numberLine);
}

However, for some reason this still lets in a duplicate, though rarely (about 1 in 50 arrays), such as 6 6 16 24 34 46. But when I try to duplicate this by taking out the random number element and using a number like 30, I am unable to reproduce the result. What's going wrong?

Answer 1

Here is what can happen. Let's say you've already drawn 1 and 2. On the third iteration you draw 1 again. What happens is that your inner loop would decrement i once, after which numberLine[i] = randomNumber will place the 1 into the second position. You now have 1, 1 in your array. QED.

Having figured out the bug, I have a couple of suggestions:

1) The following:

for(int j = 0; j < numberLine.length; j++)

should be

for(int j = 0; j < i; j++)

Otherwise you're looking at positions that are yet to be populated.

2) I'd rewrite the whole algorithm using a SortedSet: simply keep adding random numbers to the set until it has the desired size. At the end, use toArray(). This will automatically take care of the de-duplcation and the sorting, and will have a better time complexity than your current solution.

Answer 2

All the other suggestions are equally good, here is some code which I think should work:

public void populateArray()
{
    boolean OK = true;
    int i = 0;
    while (i < numberLine.length)
    {
        randomNumber = 1 + randomGen.nextInt(49);
        for(int j = 0; j < i; j++) if (numberLine[j] == randomNumber) OK = false;
        if (OK)
        {
            numberLine[i] = randomNumber;
            i++;
        }
        OK = true;
    }
    Arrays.sort(numberLine);
}

Answer 3

It would be a lot easier with collections, for example a TreeSet which is both sorted and without duplicate

Set<Integer> set = new TreeSet<Integer>();
while (set.length() < 6) {
    set.add(randomGen.nextInt(49));
} 

Use toArray() after that if you really want to have an array.

Answer 4

Actually since your domain is limited to integers between 1 and 49 it's better to use an array of booleans to indicate whether the number was already drawn:

public void populateArray()
{
    count = 0;
    boolean[] used = new boolean[50];
    while (count < 6) {
        randomNumber = 1 + randomGen.nextInt(49);
        if (!used[randomNumber]) ++count;
        used[randomNumber] = true;
    }


    int j = 0;
    for (int i = 1; i < used.length; ++i) {
        numberLine[j++] = i;
    }
}

edit

That still has potential infinite loop.

You're drawing 6 numbers out of 49 without duplicates. The correct solution would be:

 public void populateArray() {
    List<Integer> pool = new ArrayList<Integer>();
    for (int i = 0; i < 49; ++i) {
        pool.add(i + 1);
    }

    for (int i = 0; i < 6; ++i) {
        randomNumber = randomGen.nextInt(pool.size());
        numberLine[i] = pool.get(randomNumber);
        pool.remove(randomNumber);
    }

    Arrays.sort(numberLine);
}

Finite loops, the same probability distribution as the original one. Instead of retrying the draw when a duplicate is encountered you just eliminate the possibility of drawing the duplicate beforehand. It's basically emulating the real lotto-like draw.