Arrays.sort not filling array, overwriting values that are already in the array

Question

I need to generate an array int[] randomNumbers of random numbers with no duplicates. To do this, I make an array with all values that can go into randomNumbers, then use a random number generator to pick one out of the list, check if it's already in randomNumbers, and if it isn't, put it in randomNumbers.

(I want numbers between 1 and max, not 0 and max-1)

To be able to use Arrays.sort(int[]), the list needs to be sorted. So I use a third array, with the same values as randomNumbers called sortedNumbers, and sort it on every iteration:

public int[] uniqueRandom(int max, int numRequired) {
    if (max < numRequired) {
        numRequired = max;
    }
    int[] randomNumbers = new int[numRequired];
    int[] sortedNumbers = new int[numRequired];
    int[] sequentialNumbers = new int[max];
    for (int i = 1; i < max; i++) {
        sequentialNumbers[i] = i;
            System.out.println(sequentialNumbers[i]);
    }

    int p = 0;
    while (p < numRequired) {
        int j = r.nextInt(max) + 1;
        System.out.println("J:" + j);
        if (Arrays.binarySearch(sortedNumbers, j) >= 0) {
            System.out.println("Number Found:" + Arrays.binarySearch(randomNumbers,  j));
        } else {
            randomNumbers[p] = j;
            sortedNumbers[p] = j;
            Arrays.sort(sortedNumbers);
            for (int i = 0; i < randomNumbers.length; i++) {
                System.out.println("rNum[" + i + "]:" + randomNumbers[i]);
            }
            System.out.println("\n");
            for (int i = 0; i < randomNumbers.length; i++) {
                System.out.println("sNum[" + i + "]:" + sortedNumbers[i]);
            }
            p++;
        }

    }

    return randomNumbers;
}

My issue is that I'm getting an output where sortedNumbers is overwriting values. For uniqueRandom(5, 5) the output is:

J:2
rNum[0]:2
rNum[1]:0
rNum[2]:0
rNum[3]:0
rNum[4]:0

sNum[0]:0
sNum[1]:0
sNum[2]:0
sNum[3]:0
sNum[4]:2


J:2 // 2 already in the list, try again


J:2


J:4
rNum[0]:2
rNum[1]:4
rNum[2]:0
rNum[3]:0
rNum[4]:0

sNum[0]:0
sNum[1]:0
sNum[2]:0
sNum[3]:2
sNum[4]:4


J:5
rNum[0]:2
rNum[1]:4
rNum[2]:5
rNum[3]:0
rNum[4]:0

sNum[0]:0
sNum[1]:0
sNum[2]:2
sNum[3]:4
sNum[4]:5


J:2


J:3
rNum[0]:2
rNum[1]:4
rNum[2]:5
rNum[3]:3
rNum[4]:0

sNum[0]:0  // Should be:
sNum[1]:0  // 2
sNum[2]:2  // 3
sNum[3]:3  // 4
sNum[4]:5  // 5


J:4
rNum[0]:2
rNum[1]:4
rNum[2]:5
rNum[3]:3
rNum[4]:4

sNum[0]:0
sNum[1]:0
sNum[2]:2
sNum[3]:3
sNum[4]:4

So you can see the issue. I'm using java 1.7, and have no idea why it's doing this!

Answer 1

To solve your problem I would use a Set, that assure us to have unique results.

Below snipest will generate array with required number of unique integers.

Set<Integer> uniqueNumbers = new HashSet<Integer>();
Random r = new Random();
while(uniqueNumbers.size() < numRequired) {
    uniqueNumbers.add(r.nextInt(maxRandom) + 1);
} 
return uniqueNumbers.toArray(new Integer[0]);

Answer 2

There are a few issues with your code:

• since you only increment p when the new number j doesn't already exist in the arrays, that, combined with the fact that you sort the sortedArray first leads to the value actually being placed sometimes over an existing value (which shifted position due to the sort)

• I don't understand what's the use of the sequentialNumbers array...

Here's an example which should work:

private static Random r = new Random();

public static void main(String[] args) {
    System.out.println(Arrays.toString(uniqueRandom(10, 10)));
}

public static int[] uniqueRandom(int max, int numRequired) {
    if (max < numRequired) {
        numRequired = max;
    }
    int[] randomNumbers = new int[numRequired];
    int[] sortedNumbers = new int[numRequired];
    Arrays.sort(sortedNumbers);

    int p = 0;

    while (p < numRequired) {
        int j = r.nextInt(max) + 1;         
        if(Arrays.binarySearch(sortedNumbers, j)<0) {
            randomNumbers[p] = j;
            System.arraycopy(randomNumbers, 0, sortedNumbers, 0, randomNumbers.length);
            Arrays.sort(sortedNumbers);
            p++;
        }           
    }

    return randomNumbers;
}

Answer 3

While it doesn't answer the question, here is an alternative which is O(n) and work well provided max is not large.

public static void main(String[] args) {
    System.out.println(Arrays.toString(uniqueRandom(20, 10)));
}

public static int[] uniqueRandom(int max, int numRequired) {
    int[] possible = new int[max];
    int[] ret = new int[numRequired];
    for (int i = 0; i < max; i++)
        possible[i] = i + 1;
    Random r = new Random();
    int numLeft = max;
    for (int i = 0; i < numRequired; i++) {
        int idx = r.nextInt(numLeft);
        ret[i] = possible[idx];
        if (idx < --numLeft)
            possible[idx] = possible[numLeft];
    }
    return ret;
}

prints

[4, 10, 12, 19, 8, 3, 15, 1, 14, 7]

What I am trying to say is that perhaps you could make it simpler.

Answer 4

When you input J=5

the sortedNUm[] is

sNum[0]:0
sNum[1]:0
sNum[2]:2
sNum[3]:4
sNum[4]:5

next when you input J=3 (your p=3) after

sortedNumbers[p] = j;

your sNUM[3] which is 4 is replaced by 3 hence after sorting it becomes

sNum[0]:0  // Should be:
sNum[1]:0  // 2
sNum[2]:2  // 3
sNum[3]:3  // 4
sNum[4]:5  // 5

notice 4 is not present

I suggest you initialize the array to -1 or 0 and add the variables at the start of array like

sortedNumbers[0]=j;

and after Arrays.sort(); the first position will always be empty to add more numbers

Answer 5

You are putting the new number into both arrays using the same index. Your rNum array is filling from top down, but the sorted array is not: Each time you sort it, the new value moves down in the array and the zeros are always at the top. I think you could fix it by always putting the new number in the first position of the sorted array:

sortedNumbers[0] = j;