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?

it has a potential to loop infinitely, which is probably not something you'd want, see my answer on how to avoid them. — soulcheck
– soulcheck, Commented Jan 21, 2012 at 12:24
yes, the part that people suggested, the j < i part, that can loop, because both i and j start as 0, therefore j is not less than i. — Arcadian
– Arcadian, Commented Jan 21, 2012 at 13:05
It's not that. As far as I can see all other solutions use draw first, test, repeat draw on the same range technique. This leads to infinite loop - the drawing range doesn't get smaller. You can always have bad luck and draw the same number ad infinitum. — soulcheck
– soulcheck, Commented Jan 21, 2012 at 13:08

Baldrick · Accepted Answer · 2012-01-21 11:39:42Z

5

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.

answered Jan 21, 2012 at 11:39

Baldrick

24.4k6 gold badges76 silver badges80 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

NPE · Accepted Answer · 2012-01-21 11:56:55Z

4

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.

edited Jan 21, 2012 at 11:56

answered Jan 21, 2012 at 11:32

NPE

503k114 gold badges970 silver badges1k bronze badges

3 Comments

Arcadian Over a year ago

Edited to reflect suggestion one. Thanks for that, I forgot how inefficient that was.

Arcadian Over a year ago

Yes , but i'm not showing the whole class here. Do you need it all? I'll put it up if it'll help

alf Over a year ago

@Arcadian it doesn't matter actually: it's a public method, which means it can be called by anyone, anytime. For example, one can call it twice in a row. So whether some other code cleans up the array for us or not is of no relevance: the array must be considered arbitrary, no assumptions should be made.

soulcheck · Accepted Answer · 2012-01-21 13:14:23Z

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.

Dale K · Accepted Answer · 2012-01-21 11:56:16Z

1

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);
}

edited Jan 21, 2012 at 11:56

answered Jan 21, 2012 at 11:39

Dale K

28.1k15 gold badges59 silver badges86 bronze badges

3 Comments

Arcadian Over a year ago

Okay, I follow what you're doing here, using a Boolean flag. But, suppose the flag is false, that would mean that the number wouldn't be added to the array, but because of the for loop having i++, wouldn't that mean that it would still move on to the next array element?

Arcadian Over a year ago

Tried this out, seems to still infinite loop. I believe this is because of j < i. I starts out at 0, but j also starts as 0. So when it comes to the check, j is not less than i.

Dale K Over a year ago

Thats very strange as it works perfectly for me, I put it in a test script which print the good numbers and also prints the duplicates and it worked a treat. But anyway not to worry as @soulcheck's solution is much better.

Collectives™ on Stack Overflow

Check for duplicates while populating an array

4 Answers 4

Comments

3 Comments

Comments

3 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

3 Comments

Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related