# Random numbers

• June 4th, 2009, 12:38 AM
Pooja Deshpande
Random numbers
Hi All,

I have been assigned a problem of generating set of random numbers. I found out that I could use java.util.Random class for the same. But the problem is, the generated numbers should not repeat. How can I assure this?

• June 4th, 2009, 03:35 AM
JavaPF
Re: Random numbers
Good morning Pooja Deshpande,

How many random numbers do you need to generate?

You could add each random number to an array and loop through to check the previous number hasn't already been added.
• June 4th, 2009, 03:40 AM
Pooja Deshpande
Re: Random numbers

Ya I can do that, but then it would overload on the system. the efficiency won't be good was what I thought. So was trying to know if there exists an algorithm or implementation(in Java) which doesnt generate duplicates?
• June 4th, 2009, 03:55 AM
JavaPF
Re: Random numbers
Why would it overload on the system? You would have to be generating lots of numbers for that to be happening I think. How many numbers are you looking to generate?

There is no built in method in java.util.Random not to print duplicates.
• June 4th, 2009, 04:06 AM
Pooja Deshpande
Re: Random numbers
Oh ok... I guess I'm asking for too much :)

I will implement it myself, and as you pointed out, the overload would be neglible, because I'm going to generate just 30-40 numbers.

• June 4th, 2009, 04:29 AM
Dalisra
Re: Random numbers
If you need to pick numbers in random order from x to y then I agree that using random function this way would be unefficient. There are several ways of doing this depending on how big is the range (y-x).

One of them would be: You can use array from x to y, then go through it and mix number places using random function, then you will have numbers in random order.

Code :

```/** * I haven't checked if this code works, or if dosn't have any errors * so please use it more as a pseudocode than java code */ //create array int[] array = new int[100]; //lets populate our array for (int i=0; i<100;i++){ array[i] = i; } for (int i=0; i<100;i++){ //randomly generate new number int newPlace = Math.random()*100; //temporary place to hold current integer int temp = array[i]; //move new integer to current place array[i] = array[newPlace]; //move back current integer to the empty number place array[newPlace] = temp; } //now you have an array with random numbers from 0 to 99 //pick first random number int first = array[0]; //pick second random number int second = array[1]; //pick last random number int last = array[99]; }```

Also worth to mention that with very large numbers you will be using a lot of memory..
• June 4th, 2009, 04:36 AM
Dalisra
Re: Random numbers
Quote:

Originally Posted by Pooja Deshpande
Oh ok... I guess I'm asking for too much :)

I will implement it myself, and as you pointed out, the overload would be neglible, because I'm going to generate just 30-40 numbers.

You say that you will generate 30-40 numbers.. That is a lot if the range is just 40 numbers(f.e. from 1 to 40), and you would overload system. But if the range is one billion (f.e. from 1 to 1 000 000 000 000) Then you must be lucky to strike even one of those numbers twice. So for my second example you will have no system overload.

So for us to be able to help you, you need to tell exactly what you need it for.
• June 5th, 2009, 03:36 AM
Freaky Chris
Re: Random numbers
Quote:

Originally Posted by Dalisra
If you need to pick numbers in random order from x to y then I agree that using random function this way would be unefficient. There are several ways of doing this depending on how big is the range (y-x).

One of them would be: You can use array from x to y, then go through it and mix number places using random function, then you will have numbers in random order.

Code :

```/** * I haven't checked if this code works, or if dosn't have any errors * so please use it more as a pseudocode than java code */ //create array int[] array = new int[100]; //lets populate our array for (int i=0; i<100;i++){ array[i] = i; } for (int i=0; i<100;i++){ //randomly generate new number int newPlace = Math.random()*100; //temporary place to hold current integer int temp = array[i]; //move new integer to current place array[i] = array[newPlace]; //move back current integer to the empty number place array[newPlace] = temp; } //now you have an array with random numbers from 0 to 99 //pick first random number int first = array[0]; //pick second random number int second = array[1]; //pick last random number int last = array[99]; }```

Also worth to mention that with very large numbers you will be using a lot of memory..

EDIT: If you choose to use this method then I suggest you use the Knuth Shuffle/Fisher-Yates Shuffle. The code that they present is as follows
Code :

```public static void shuffle (int[] array) { Random rng = new Random(); // i.e., java.util.Random. int n = array.length; // The number of items left to shuffle (loop invariant). while (n > 0) { n--; // n is now the last pertinent index; int k = rng.nextInt(n + 1); // 0 <= k <= n. if ( n != k ) { int tmp = array[k]; array[k] = array[n]; array[n] = tmp; } } }```
This is one of the best Shuffling methods out there, it presents the closest to real random as possible within a good exectution time.

This approach is very good. However if you are looking for one that uses less memory but takes a little longer to execute then perhaps you could do something like this

Code :

```import java.util.Random;   public class RandomGen { public static void main(String[] args){ Random rng = new Random(); int n = 50, x; boolean[] repeat = new boolean[n+1]; for(int i = 1;i<=n;){ x = rng.nextInt(n+1); if(!repeat[x]){ repeat[x] = true; System.out.println((i++) + ": " + x + " : " + repeat[x]); }else x = rng.nextInt(n+1); } } }```
Which uses a boolean array which ofcouse saves on alot of space in comparision to an int array or even a long array if you are after bigger numbers. The downside is it may take more than one attempt to find a number that hasn't already been generated.

Regards,
Chris
• June 5th, 2009, 04:36 AM
JavaPF
Re: Random numbers
Good post Chris. ~o)