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?
Thanks In Advance!:)
Printable View
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?
Thanks In Advance!:)
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.
thanks for the reply!
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?
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.
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.
Thanks for the reply!
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..
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.
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 followsThis is one of the best Shuffling methods out there, it presents the closest to real random as possible within a good exectution time.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 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
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.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); } } }
Regards,
Chris
Good post Chris. ~o)