Best practise for random generator Java

Question

Having an array of numbers I want to randomly pick every index of it with a random generator. What is the best practise for the random generator to avoid useless loops on indexes that have already selected? So far I use an ArrayList tho store the already selected ones but I feel that in the end this algorithm will have many wasted loops in the end. Here is the code:

Random r = new Random();
ArrayList<Integer> found = new ArrayList<Integer>();
while(notAllPassed){
   int prediction = r.nextInt(sizeOfArray);
   if(!found.contains(prediction){
      found.Add(prediction);
      //Do stuff
   }
}

To expand a little on what @MarkoTopolnik said (in case it is not obvious). Search for shuffling algorithm. — markbernard, Nov 09 '16 at 12:46
You can also use HashSet to store the random number instead of first storing it in ArrayList — Shreyas Sarvothama, Nov 09 '16 at 12:47
@MarkoTopolnik LOL, been in the Collections class so many times and never noticed that. — markbernard, Nov 09 '16 at 12:48
Yes the shuffle idea is very good thanks.put it as an aswer so I can vote it — i_ll_be_back, Nov 09 '16 at 12:48
Possible duplicate of [How to randomize ArrayList?](http://stackoverflow.com/questions/4228975/how-to-randomize-arraylist) — Matsemann, Nov 09 '16 at 13:08

score 4 · Accepted Answer · answered Nov 09 '16 at 12:52

The idea is, instead of choosing a random index each time, to prepare a shuffled list of all indices and just iterate over it in order.

List<Integer> indices = IntStream.range(0, sizeOfArray).boxed().collect(toList());
Collections.shuffle(indices);
for (int randomIndex : indices) {
   // do your thing
}

score 3 · Answer 2 · answered Nov 09 '16 at 12:48

Instead of checking if you have things already generated, approach it differently. Create an array of all possible values and then shuffle the array randomly.

You can utilize built-in method java.util.Collection.shuffle(List)

For the initial list, order doesn't matter, but it is easiest to just fill it with 0..n-1 or 1..n values one after another. Doing it in more complex way is not helping in any way, as shuffle is anyway fully random.

score 0 · Answer 3 · edited May 23 '17 at 11:53

Marko Topolnik is absolutly right with his answer. Thats the best way to do it.

So my answer is just for the sake of completion, following your initial idea with Random

    Random r = new Random();                      // as you had it
    ArrayList<Integer> found = new ArrayList<>(); // as you had it

    for(int i = 0; i < sizeOfArray; i++){         // if you want ALL possible indexes 
        int prediction = r.nextInt(sizeOfArray);  // exactly as you did it
        while(found.contains(prediction)){        // here we check if the "found" list already contains the random index
            prediction = r.nextInt(sizeOfArray);  // if so, regenerate the "prediction" until one is generated that is not in the list
        }
        found.add(prediction);                    // this statement will only be reached after the while loop found an index that is not in the list
    }

    System.out.println(found.toString());         // convenience: print the list to see for yourself

As I said, this is just following your initial idea to use random. I would have done it this way, if there was no Collection.shuffle() :)

Best practise for random generator Java

3 Answers3