Java Array of unique randomly generated integers

for (int i = 0; i < size; i++) {
    a[i] = (int)(Math.random()*10);

    for (int j = 0; j < i; j++) {
        if (a[i] == a[j]) {
            a[j] = (int)(Math.random()*10); //What's this! Another random number!
        }
    }   
}

You do find the duplicate values. However, you replace it with another random number that may be a duplicate. Instead, try this:

for (int i = 0; i < size; i++) {
    a[i] = (int)(Math.random()*10);//note, this generates numbers from [0,9]

    for (int j = 0; j < i; j++) {
        if (a[i] == a[j]) {
            i--; //if a[i] is a duplicate of a[j], then run the outer loop on i again
            break;
        }
    }  
}

However, this method is inefficient. I recommend making a list of numbers, then randomizing it:

ArrayList<Integer> a = new ArrayList<>(11);
for (int i = 0; i <= 10; i++){ //to generate from 0-10 inclusive. 
                               //For 0-9 inclusive, remove the = on the <=
    a.add(i);
}
Collections.shuffle(a);
a = a.sublist(0,4);
//turn into array

Or you could do this:

ArrayList<Integer> list = new ArrayList<>(11);
for (int i = 0; i <= 10; i++){
    list.add(i);
}
int[] a = new int[size];
for (int count = 0; count < size; count++){
    a[count] = list.remove((int)(Math.random() * list.size()));
}

It might work out faster to start with a sequential array and shuffle it. Then they will all be unique by definition.

Take a look at Random shuffling of an array, and at the Collections.shuffle function.

int [] arr = [1,2,3,.....(size)]; //this is pseudo code

Collections.shuffle(arr);// you probably need to convert it to list first

If you have a duplicate you only regenerate the corresponding number once. But it might create another duplicate. You duplicate checking code should be enclosed in a loop:

while (true) {
    boolean need_to_break = true;
    for (int j = 0; j < i; j++) {
        if (a[i] == a[j]) {
            need_to_break = false; // we might get another conflict
            a[j] = (int)(Math.random()*10);
        }
    }
    if (need_to_break) break;
}

But make sure that size is less than 10, otherwise you will get an infinite loop.

Edit: while the above method solves the problem, it is not efficient and should not be used for large sized arrays. Also, this doesn't have a guaranteed upper bound on the number of iterations needed to finish.

A better solution (which unfortunately only solves second point) might be to generate a sequence of the distinct numbers you want to generate (the 10 numbers), randomly permute this sequence and then select only the first size elements of that sequence and copy them to your array. You'll trade some space for a guarantee on the time bounds.

int max_number = 10;
int[] all_numbers = new int[max_number];
for (int i = 0; i < max_number; i++)
    all_numbers[i] = i;

/* randomly permute the sequence */
for (int i = max_number - 1; i >= 0; i--) {
    int j = (int)(Math.random() * i); /* pick a random number up to i */

    /* interchange the last element with the picked-up index */
    int tmp = all_numbers[j];
    all_numbers[j] = a[i];
    all_numbers[i] = tmp;
}

/* get the a array */
for (int i = 0; i < size; i++)
    a[i] = all_numbers[i];

Or, you can create an ArrayList with the same numbers and instead of the middle loop you can call Collections.shuffle() on it. Then you'd still need the third loop to get elements into a.

Java Array of unique randomly generated integers

Related

Recent Posts