Issue with randomize method

Question

I have a method that is not working properly. The method is supposed to sort a set of numbers from 1 to 20 randomly (each number must appear just once). My issue here is that when I run the program, some numbers are repeated several times. The code is the following:

public static int randomize(int index) {

    //This array will hold the 20 numbers.
    int[] randomIndex = new int[20];

    Random ranNum = new Random();

    for (int x = 0; x<20; x++) {
        int temp;

        //The number is generated randomly and saved in temp.
        temp = ranNum.nextInt(20);

        //This loop skips the first index.
        if (x != 0){

            /*Here, the loop is supposed to compare a generated number with
            the previous one*/
            for (int y = 1; y<=x; y++) {


                while(temp == randomIndex[x-y] ) {

                    /*If the while loop finds that temp variable matches any previous                          
                    number it will generate another random number for it until it finds
                    no matches.*/
                    temp = ranNum.nextInt(20);

                }  
            }
        }

    /*Once no match has been found for temp, the number is assigned to an index, 
    and the loop is executed with a x variable increment.
    randomIndex[x] = temp;

    }
   //Finally the array with the set of random numbers is sent to the main function.
   return randomIndex[index];

  }

And I got the following output:

19, 19, 5, 16, 6, 2, 18, 1, 15, 1, 5, 19, 11, 4, 18, 0, 5, 18, 10.

So now I have no idea what to do. :C

Answer 1

When you use Random.nextInt(), there's no guarantee that the numbers generated are unique. You should generate numbers from 1 to 20 first, then shuffle the numbers. Now the question is changed to "How to shuffle the numbers randomly?"

Perhaps you can refer the implementation of JDK Collections.shuffle().

The algorithm for shuffling the numbers are simple:

1. Pick first element in the array and swap it with a number at random position.
2. Repeat step 1 until the last element.

Answer 2

I edited your function for generate array from 1 to 20:

public static int[] randomize() {

    int[] randomIndex = new int[20];

    Random ranNum = new Random();
    boolean isAlreadyIn;
    boolean isZero;
    int x = 0;

    while (x < 20) {
        isAlreadyIn = false;
        isZero = false;
        int temp;
        temp = ranNum.nextInt(21);
        for(int i = 0; i < randomIndex.length; i++){
            if(temp == 0)
                isZero = true;
            if(temp == randomIndex[i])
                isAlreadyIn = true;
        }
        if (!isZero && !isAlreadyIn){
            randomIndex[x] = temp;
            x++;
        }
    }

   return randomIndex;
}

hope it will be helpful.

Answer 3

It looks like you're trying to generate your random numbers by rejection -- that is, by comparing each random number with all previously accepted numbers, and re-generating new ones until you find one that is is different from all of them.

As others have mentioned, it would be far more efficient to generate the numbers from 1 to 20, and shuffle them with a random permutation. However, if implemented correctly, your approach should work... eventually.

A random shuffle implementation might look something like this:

for(int i=0; i<20; i++) {  // index goes from 0..19
  randomIndex[i] = i + 1;  // value goes from 1..20
}

for(int i=0; i<20; i++) {
  int j = i + ranNum.nextInt(20 - i);  // choose random j from i <= j < 20
  int temp = randomIndex[i];           // swap elements i and j
  randomIndex[i] = randimIndex[j];
  randomIndex[j] = temp;
}

---

The are two reasons why your posted code generates duplicates. First, when you reject a candidate random number and re-generate a new one, you need to compare it against all existing numbers, restarting you inner (y) loop from the beginning. Your existing code doesn't do that.

Second, I believe that the new Random() constructor generates a different seed each time it is called. If so, your randomize() function is generating a completely different random list each time, and returning the selected index from it. In any case, it makes more sense to return the entire array, instead.

Answer 4

You can avoid it by using something like this:

   final Random random = new Random();


    final HashSet<Integer> integers = new HashSet<>();

    while(integers.size() < 20) {
        integers.add(random.nextInt(20));
    }

    System.out.println(integers);