Generate an array containing unique Random ints, check for duplicates

Question

This is an assignment for school that I am really close to completing, but I don't have it exactly. I am supposed to generate an array of integer Nodes with 100 random numbers without duplicates by checking for duplicates. I'm not allowed to use a Set. I'm not allowed to just shuffle an array of numbers 1-1000.

Here is the code I have in my client class so far but it still creates duplicates:

for (int i = 0; i < SIZE; i++) {
    int j = (int)(Math.random()*1999);

 //put a random number in the first index.
    if (i == 0) {
        Node newNode = new Node(j);
        nodeArray[i] = newNode;
    }

    for (int k = 0; k < i; k++) {
        if (nodeArray[k].getInt() == j) {
            j = (int)(Math.random()*1999);
            break;
        } else {
            Node newNode = new Node(j);
            nodeArray[i] = newNode;
        }
    }
}

If you find a duplicate it is not enough to just select a new number. You have to check the new number also as that could be a duplicate. Basically, when at index i, keep generating random numbers until you find one that is not used on position 0..i-1. When found, assign to index i and repeat for i+1. — Roger Lindsjö
– Roger Lindsjö, Commented Feb 5, 2014 at 18:06
@RogerLindsjö So change my inner most if statement to a while? Would that help fix it? — Maggie S.
– Maggie S., Commented Feb 5, 2014 at 18:07
@MagdaleneB. check my answer please. it is easy to understand. — Juvanis
– Juvanis, Commented Feb 6, 2014 at 8:48

M21B8 · Accepted Answer · 2014-02-05 18:08:16Z

The way i would do this would be to use a List to store all the random numbers in. Then when you generate a number you can check if it already exists in the list, and get another number (this is done via recursion, or a while loop). You keep going with this until your list is full. Then go through the list creating the Nodes for your array.

List<Integer> numbers = new ArrayList<Integer>(SIZE);
for (int i = 0;i<SIZE; i++) {
    addUniqueRandomNumber(numbers, SIZE*2);
}

for (int i =0;i<numbers.size; i++) {
  Node newNode = new Node(numbers.get(i));        
  nodeArray[i] = newNode;
}

The addUniqueRandomNumber method:

public static void addUniqueRandomNumber(List<Integer> numbers, int range) {
    int j = (int)(Math.random()*range);
    if (numbers.contains(j)) {
        addUniqueRandomNumber(numbers, range);
    } else {
        numbers.add(j);
    }
}

jrowe08 · Accepted Answer · 2014-02-05 18:10:42Z

Because when you are assigning a new random if the first random is a duplicate in your second if statement it never checks if that random could be also a duplicate. You need to redo the loop and check if that number is a duplicate as well.

for (int k = 0; k < i; k++) {
    if (nodeArray[k].getInt() == j) {
        j = (int)(Math.random()*1999); //You must check if this random is also a dup
        break;
    } else {
        Node newNode = new Node(j);
        nodeArray[i] = newNode;
    }

Here's what I would do:

int i = 0;
while (i < SIZE) {
int j = (int)(Math.random()*1999);

 //put a random number in the first index.
if (i == 0) {
    Node newNode = new Node(j);
    nodeArray[i] = newNode;
    i++;
}

for (int k = 0; k < i; k++) {
    if (nodeArray[k].getInt() == j) {
        //Do nothing
    } else {
        Node newNode = new Node(j);
        nodeArray[i] = newNode;
        i++;
    }
  }
}

Basically only increment i if the number is not duplicate, otherwise go through and try to find another random that is not a duplicate.

Ashot Karakhanyan · Accepted Answer · 2014-02-05 18:48:28Z

1

Solution algorithm which check after each generated number exist is or no:

int[] nodeArray = new int[100];
int currentIndex = 0;

while(currentIndex < 100) {
    int currentValue = (int) (Math.random() * 199);
    int i = 0;
    while(i < currentIndex) {
        if(currentValue == nodeArray[i]) {
            break;
        }
        i++;
    }
    if(i == currentIndex) {
        nodeArray[currentIndex++] = currentValue;
    }
}

Then you can sort ant print random numbers

Arrays.sort(nodeArray); // Sort to be easy find duplicates
for (Integer i : nodeArray) {
    System.out.print(i + ", ");
}

edited Feb 5, 2014 at 18:48

answered Feb 5, 2014 at 18:42

Ashot Karakhanyan

2,8283 gold badges26 silver badges29 bronze badges

Comments

Juvanis · Accepted Answer · 2014-02-06 08:49:26Z

1

I suggest to use a helper boolean array to keep track of which numbers were already added to the array. Review this code, it is short and concise:

boolean[] used = new boolean[2000];
int[] randomUniqueIntegers = new int[SIZE];

for (int i = 0; i < SIZE; i++) {
    int num = (int) (Math.random() * 1999);

    if (!used[num]) {
        used[num] = true;
        randomUniqueIntegers[i] = num;
    } else {
        while (used[num]) {
            num = (int) (Math.random() * 1999);
            if (!used[num]) {
                used[num] = true;
                randomUniqueIntegers[i] = num;
                break;
            }
        }
    }
}

As you see the implementation above doesn't use Set or shuffling. However, you can use the test code below to see it works correctly.

Set<Integer> set = new HashSet<Integer>();
for (int i : randomUniqueIntegers)
    set.add(i);
System.out.println(set.size());

You will see that the size of the set is equal to SIZE constant in each run which indicates we have all unique elements in our array.

edited Feb 6, 2014 at 8:49

answered Feb 5, 2014 at 18:24

Juvanis

26k5 gold badges74 silver badges88 bronze badges

2 Comments

jrowe08 Over a year ago

What does while (used[num]) iterate?

Juvanis Over a year ago

@jrowe08 it doesnt iterate over sth, it just tries to find a non-used integer, when it is found while loop breaks.

Collectives™ on Stack Overflow

Generate an array containing unique Random ints, check for duplicates

4 Answers 4

Comments

Comments

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

Comments

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related