how to avoid repetition and zero's with java random function?

Question

I have an array that contains 100 elements, I want to print out 20 random elements without repetition or having zeros.

I have successfully printed a random set of 20 numbers out of a 1000 but I cannot stop it from printing out the repetitions and/or zeros. Any help?!

Here is the code :-

import java.util.Random;


public class MyClass {
    public static void main(String args[]) {
        int[] persons = new int[1000];
        int[] person  = new int[20];
        Random random = new Random();

        for (int i = 0; i < person.length; i++)
        {
            person[i] = random.nextInt(persons.length);
            System.out.println(person[i]);
        }
    }
}

Answer 1

_{This question may break the APH-record (Answers Per Hour), with 8 answers in the first hour. Usually, this is a bad sign, but surprisingly, I didn't find the question that I would have liked to delcare this one a duplicate of.}

Unfortunately, most "simple" answers may have severe drawbacks in practice. Most importantly, the proposed solutions are either inefficient for certain setups, or employ techniques where you can not prove the Total Correctness - namely, the algorithms may not be proven to terminate. This refers to the approaches that boil down to adding random numbers to a Set and use this Set to keep track of the number of distinct elements that have been chosen. So, for example, in this code

Set<Integer> set = new HashSet<Integer>();
Random random = new Random(0);  
while (set.size() < sampleSize) {
    set.add(min + rand.nextInt(max));
}

the loop might never terminate. You simply can not prove that there will ever be 20 distinct numbers chosen. The Random instance might return 0 in the first call. And it might return 0 in the second call. And in the third call....you can never be sure.

---

Of course, "in practice", the loop usually will terminate, sooner or later, but this depends on the parameters: When it is requested to pick 20 distinct random numbers between 0 and 10, it will not terminate. The same applies for similar techniques, like

int[] ints = new Random(0).ints(0, 10).distinct().limit(20).toArray();

So the parameters should carefully be checked, to make sure that they are valid in this regard.

---

The other option that is often suggested in various forms is to use Collections#shuffle on a list that is pre-filled with the items to choose from. This may be applicable for your case, where this list may have only 100 or 1000 elements. But filling a list, with, say 100000000 elements is too memory consuming, and shuffling this list too time consuming.

---

There is a rather versatile technique for solving this in general. It is referred to as Reservoir Sampling.

_{(Note that there are some questions regarding implementations of reservoir sampling, but it did not seem to be proposed as the solution for this very generic task)}

Here is an implementation of reservoir sampling in Java. For a given sample size and range, it returns a collection of (random, unique) integers in the desired range, in ascending order:

/**
 * Creates a collection with the given size, containing random values 
 * between the given minimum value (inclusive) and maximum value
 * (exclusive). The resulting collection will contain the values
 * in ascending order. 
 *  
 * @param size The size of the returned collection
 * @param min The minimum value (inclusive)
 * @param max The maximum value (exclusive)
 * @param random The random number generator
 * @return The collection
 * @throws IllegalArgumentException If the requested size is larger than
 * the difference between the maximum value and the minimum value
 */
public static Collection<Integer> randomSample(
    int size, int min, int max, Random random)
{
    if (size > max - min)
    {
        throw new IllegalArgumentException(
            "Can not create a sample of size "+size+
            " with values between "+min+" and "+max);

    }
    Set<Integer> set = new LinkedHashSet<Integer>(size);
    int n = size;
    for (int i = 0; i < max - min; i++)
    {
        double d = (double) size / ((max - min) - i);
        if (random.nextDouble() < d)
        {
            set.add(i + min);
            n--;
        }
        if (n <= 0)
        {
            break;
        }
    }
    return set;
}        

_{(If there are any flaws or shortcomings with this implementation, drop me a note in the comments).}

This can serve as a building block for similar tasks. For example, in your case, you could create a random sample of indices, and use this to pick the desired elements:

int persons[] = new int[1000];
int sample[]  = new int[20];
Collection<Integer> indices = randomSample(20, 0, 1000);
int n = 0;
for (Integer index : indices) 
{
    sample[n] = index;
    n++;
}

For other cases, you might want to create a list from the returned indices and shuffle this list. But in this case, only the (small) sample would have to be shuffled, and not the (potentially large) list containing all possible inputs.

Answer 2

It is meant to have repetition of random numbers. For security reasons, if you don't have repetition, next numbers can be guessed by simple having previous numbers.

To conclude, any good written random function is returning repeated numbers after few numbers generated.

So, you are actually looking for some method to shuffle already selected elements. Collections.shuffle() can do the trick.

Answer 3

import java.util.Random;


public class MyClass {
    public static void main(String args[]) {
        int[] persons = new int[1000];
        int[] person  = new int[20];
        Random random = new Random();

        for (int i = 0; i < person.length; i++)
        {
            int number = random.nextInt(persons.length);
            while(number == 0 || IntStream.of(person).anyMatch(x -> x == number))
                number = random.nextInt(persons.length);
            person[i] = number;
            System.out.println(person[i]);
        }
    }
}

Be careful here, if you only have repetitions left or 0s in the array, you could get into an infinite loop!

Other ways to make to array contain only unique elements before you run random through it: How to get unique items from an array?

[EDIT]

Some explanations about the code IntStream.of(person).anyMatch(x -> x == number). Here we are taking your result array and stream it to be able to use a predicate to filter it. We are checking if the value of number has appeared before in the array person. If so, we do not want to use that number so we just do another random number getter from the persons array.

Answer 4

Small idea

You can each time shuffle the list and take first 20th items. you will make sure no repetitions and no zeros.

You can use Collections.shuffle(yourList)

Answer 5

You could create N distinct random indices and use them to select the elements:

int[] indices = ThreadLocalRandom.current()
    .ints(0, persons.length)
    .distinct()
    .limit(N)
    .toArray();

Answer 6

How about using HashSet?

import java.util.HashSet;
import java.util.Random;
import java.util.Set;

public class NonRepeatRandom {
    public static void main(String[] args){
        final int low = 1;
        Set<Integer> set = new HashSet<Integer>();
        Random rand = new Random();  

        while (set.size() < 20) {
            set.add(rand.nextInt(1000) + low); // set bound between 1 and 1000
        }
        System.out.println(set);
    }
}

Answer 7

//shuffle your array

int[] filteredPersons = Arrays.stream(persons).filter(x-> x!=0).distinct().limit(20).toArray();

//print here

Arrays.stream(persons).filter(x -> x!=0).distinct().limit(20).forEach(System.out::println);

// if you just want to print