Java generating non-repeating random numbers

Question

I want to create a set of random numbers without duplicates in Java.

For example I have an array to store 10,000 random integers from 0 to 9999.

Here is what I have so far:

import java.util.Random;
public class Sort{

    public static void main(String[] args){

        int[] nums = new int[10000];

        Random randomGenerator = new Random();

        for (int i = 0; i < nums.length; ++i){
            nums[i] = randomGenerator.nextInt(10000);
        }
    }
}

But the above code creates duplicates. How can I make sure the random numbers do not repeat?

possible duplicate of Generate unique random numbers in Java — JB Nizet
– JB Nizet, Commented Apr 14, 2013 at 14:35
But if you remove repeated numbers, then they're not as random — 000
– 000, Commented Apr 14, 2013 at 14:37
Do you want all 10.000 numbers in the array in a random order, or do you want 10.000 random numbers? because you can't have 10.000 random numbers within the range of 0 - 9.999 (then they are not random anymore) — GameDroids
– GameDroids, Commented Apr 14, 2013 at 14:40
Yeah I just do not want them to repeat that is the most important thing. — Fernando Martinez
– Fernando Martinez, Commented Apr 14, 2013 at 14:51
Do you want it not to repeat in the way of "1 1 2" repeats? Is "1 2 1" an acceptable sequence? — user289086
– user289086, Commented Apr 14, 2013 at 15:50

Achintya Jha · Accepted Answer · 2013-04-14 14:42:56Z

50

Integer[] arr = {...};
Collections.shuffle(Arrays.asList(arr));

For example:

public static void main(String[] args) {
    Integer[] arr = new Integer[1000];
    for (int i = 0; i < arr.length; i++) {
        arr[i] = i;
    }
    Collections.shuffle(Arrays.asList(arr));
    System.out.println(Arrays.toString(arr));

}

edited Apr 14, 2013 at 14:42

answered Apr 14, 2013 at 14:35

Achintya Jha

12.9k2 gold badges30 silver badges40 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Martinsos Over a year ago

Shuffle is great but first you should create array that contains numbers from 0 to 9999 and then shuffle it. Also, what is the time complexity of shuffle?

Achintya Jha Over a year ago

@Martinsos I created array and shuffled it. I am not sure but I think time complexity of shuffle should be O(n). Because if just do swapping randomly inside an array.

the · Accepted Answer · 2015-04-20 14:04:33Z

10

A simple algorithm that gives you random numbers without duplicates can be found in the book Programming Pearls p. 127.

Attention: The resulting array contains the numbers in order! If you want them in random order, you have to shuffle the array, either with Fisher–Yates shuffle or by using a List and call Collections.shuffle().

The benefit of this algorithm is that you do not need to create an array with all the possible numbers and the runtime complexity is still linear O(n).

public static int[] sampleRandomNumbersWithoutRepetition(int start, int end, int count) {
    Random rng = new Random();

    int[] result = new int[count];
    int cur = 0;
    int remaining = end - start;
    for (int i = start; i < end && count > 0; i++) {
        double probability = rng.nextDouble();
        if (probability < ((double) count) / (double) remaining) {
            count--;
            result[cur++] = i;
        }
        remaining--;
    }
    return result;
}

answered Apr 20, 2015 at 14:04

the

3614 silver badges9 bronze badges

5 Comments

Erwin Bolwidt Over a year ago

Note: (re: your "Attention" section) Collections.shuffle is doing a Fisher-Yates shuffle, so it's not an "either-or" situation.

the Over a year ago

You are right, Collections.shuffle does a Fisher-Yates shuffle, but you need a List to use it. Arrays.asList needs the array to be of type Integer instead of int to do the conversion correctly, then you do not have to allocate additional memory. Writing the Fisher-Yates shuffle yourself avoids the conversion and no additional memory is needed.

brain storm Over a year ago

just trying to understand why probability < ((double) count) / (double) remaining is needed? why not fill the array from start to end and just shuffle?

Ricardo Marimon Over a year ago

This answer does not get the credit it deserves. Been doing some histograms on the results to check for randomnes, and so far the results are as evenly spread as expected. For example, there is no noticeable differences between sampleRandomNumbersWithoutRepetition(0, 100, 1) and Math.floor(Math.random()*100).

Andy Turner Over a year ago

@brainstorm this approach avoids building the whole array. For example, if you only want 5 numbers in the range 0..1000, this avoids the effort of creating 995 things you are going to discard.

rollstuhlfahrer · Accepted Answer · 2018-04-26 06:38:07Z

6

In Java 8, if you want to have a list of non-repeating N random integers in range (a, b), where b is exclusive, you can use something like this:

Random random = new Random();
List<Integer> randomNumbers = random.ints(a, b).distinct().limit(N).boxed().collect(Collectors.toList());

edited Apr 26, 2018 at 6:38

rollstuhlfahrer

4,0789 gold badges28 silver badges38 bronze badges

answered Apr 26, 2018 at 5:51

Slawomir Domagala

1041 silver badge3 bronze badges

2 Comments

Torben Over a year ago

That's the equivalent of "random.ints(a, b).boxed().distinct().mapToInt(i -> i).limit(N).boxed().collect(...)". Not too eficient. Also, under the hood it is the same implmentation as Vaibhav Jain's, requiring 500500 iterations for 1000 elements. Please take the time to understand the libraries you use.

Slawomir Domagala Over a year ago

@Torben Actually, the probability to find the proper random number on each iteration is given by (N-n+1)/N in the Vaibhav Jain implementation. Where N is the total number requested random numbers and n is the number of current iteration. The expected number of iterations is then given by O(N log(N)), which on average is less than 500500. See en.wikipedia.org/wiki/Coupon_collector%27s_problem

Benjamin Brumfield · Accepted Answer · 2013-05-20 18:35:40Z

Achintya Jha has the right idea here. Instead of thinking about how to remove duplicates, you remove the ability for duplicates to be created in the first place.

If you want to stick with an array of ints and want to randomize their order (manually, which is quite simple) follow these steps.

create array of size n.
loop through and initialize each value at index i to the value i (or i+1 if you wish to have the numbers 1 to n rather than 0 to n-1).
finally, loop through the array again swapping each value for a value at a random index.

Your code could be modified to look like this:

import java.util.Random;

public class Sort
{
    // use a constant rather than having the "magic number" 10000 scattered about
    public static final int N = 10000;

    public static void main(String[] args)
    {
        //array to store N random integers (0 - N-1)
        int[] nums = new int[N];

        // initialize each value at index i to the value i 
        for (int i = 0; i < nums.length; ++i)
        {
            nums[i] = i;
        }

        Random randomGenerator = new Random();
        int randomIndex; // the randomly selected index each time through the loop
        int randomValue; // the value at nums[randomIndex] each time through the loop

        // randomize order of values
        for(int i = 0; i < nums.length; ++i)
        {
             // select a random index
             randomIndex = randomGenerator.nextInt(nums.length);

             // swap values
             randomValue = nums[randomIndex];
             nums[randomIndex] = nums[i];
             nums[i] = randomValue;
        }
    }
}

And if I were you I would likely break each of these blocks into separate, smaller methods rather than having one large main method.

Hope this helps.

user3760016 · Accepted Answer · 2017-11-08 07:26:59Z

3

If you need generate numbers with intervals, it can be just like that:

Integer[] arr = new Integer[((int) (Math.random() * (16 - 30) + 30))];
for (int i = 0; i < arr.length; i++) {
arr[i] = i;
}
Collections.shuffle(Arrays.asList(arr));
System.out.println(Arrays.toString(arr));`

The result:

[1, 10, 2, 4, 9, 8, 7, 13, 18, 17, 5, 21, 12, 16, 23, 20, 6, 0, 22, 14, 24, 15, 3, 11, 19]

Note:

If you need that the zero does not leave you could put an "if"

edited Nov 8, 2017 at 7:26

user3760016

1033 bronze badges

answered Dec 12, 2016 at 1:55

Marcus person

311 bronze badge

Comments

olz · Accepted Answer · 2021-03-17 21:28:13Z

1

A simple stream solution:

   new Random().ints(0, 10000)
        .distinct()
        .limit(10000)
        .forEach(System.out::println);

answered Mar 17, 2021 at 21:28

olz

1361 silver badge3 bronze badges

Comments

Jitin Kodian · Accepted Answer · 2016-04-28 09:48:46Z

0

How about this?

LinkedHashSet<Integer> test = new LinkedHashSet<Integer>();
Random random = new Random();
do{
    test.add(random.nextInt(1000) + 1);
}while(test.size() != 1000);

The user can then iterate through the Set using a for loop.

answered Apr 28, 2016 at 9:48

Jitin Kodian

5411 gold badge5 silver badges14 bronze badges

Comments

F. Müller · Accepted Answer · 2020-12-04 17:55:09Z

0

public class RandomNum {
    public static void main(String[] args) {
        Random rn = new Random();
        HashSet<Integer> hSet = new HashSet<>();
        while(hSet.size() != 1000) {
            hSet.add(rn.nextInt(1000));
        }
        System.out.println(hSet);
    }
}

edited Dec 4, 2020 at 17:55

F. Müller

4,0629 gold badges44 silver badges53 bronze badges

answered Dec 4, 2020 at 13:04

K D

3093 silver badges11 bronze badges

Comments

Dhwanil Patel · Accepted Answer · 2021-02-10 10:48:49Z

0

If you're using JAVA 8 or more than use stream functionality following way,

Stream.generate(() -> (new Random()).nextInt(10000)).distinct().limit(10000);

edited Feb 10, 2021 at 10:48

answered Nov 10, 2020 at 5:06

Dhwanil Patel

2,6031 gold badge20 silver badges29 bronze badges

Comments

yome fisseha · Accepted Answer · 2021-03-09 23:34:37Z

Here we Go!

public static int getRandomInt(int lower, int upper) {
    if(lower > upper) return 0;
    if(lower == upper) return lower;
    int difference = upper - lower;
    int start = getRandomInt();
    
    //nonneg int in the range 0..difference - 1
    start = Math.abs(start) % (difference+1);
    
    start += lower;
    return start;
}

public static void main(String[] args){
    
    List<Integer> a= new ArrayList();
    
    int i;
    int c=0;
    for(;;) {
        c++;
        i= getRandomInt(100, 500000);
        if(!(a.contains(i))) {
            a.add(i);
            if (c == 10000) break;
            System.out.println(i);
        }
        
        
    }
    
    for(int rand : a) {
        System.out.println(rand);
    }
    
    
    
}

Get Random number Returns a random integer x satisfying lower <= x <= upper. If lower > upper, returns 0. @param lower @param upper @return

In the main method I created list then i check if the random number exist on the list if it doesn't exist i will add the random number to the list

It is very slow but straight forward.

Jaap · Accepted Answer · 2014-07-11 07:24:21Z

-1

public class Randoms {

static int z, a = 1111, b = 9999, r;

public static void main(String ... args[])
{
       rand();
}

    public static void rand() {

    Random ran = new Random();
    for (int i = 1; i == 1; i++) {
        z = ran.nextInt(b - a + 1) + a;
        System.out.println(z);
        randcheck();
    }
}

private static void randcheck() {

    for (int i = 3; i >= 0; i--) {
        if (z != 0) {
            r = z % 10;
            arr[i] = r;
            z = z / 10;
        }
    }
    for (int i = 0; i <= 3; i++) {
        for (int j = i + 1; j <= 3; j++) {
            if (arr[i] == arr[j]) {
                rand();
            }
        }

    }
}
}

edited Jul 11, 2014 at 7:24

Jaap

83.7k36 gold badges190 silver badges203 bronze badges

answered Jul 11, 2014 at 7:07

jayanthanantharapu

2310 bronze badges

Comments

Ori Dar · Accepted Answer · 2018-09-20 10:38:38Z

-1

HashSet<Integer>hashSet=new HashSet<>();
Random random = new Random();
//now add random number to this set
while(true)
{
    hashSet.add(random.nextInt(1000));
    if(hashSet.size()==1000)
        break;
}

edited Sep 20, 2018 at 10:38

Ori Dar

19.1k5 gold badges61 silver badges76 bronze badges

answered Sep 20, 2018 at 9:39

Vaibhav Jain

1

Collectives™ on Stack Overflow

Java generating non-repeating random numbers

12 Answers 12

2 Comments

5 Comments

2 Comments

Comments

Comments

Comments

Comments

Comments

Comments

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

12 Answers 12

2 Comments

5 Comments

2 Comments

Comments

Comments

Comments

Comments

Comments

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related