Post Reply

generating non repeatable numbers

25th August 2014, 01:44 PM   |  #1  
OP Junior Member
Thanks Meter: 0
 
2 posts
Join Date:Joined: Aug 2014
I am requesting for a code that generates a random number from 0-100. for example it generates 55. then 55 won't be generated anymore unless the application exits or restarts.
25th August 2014, 04:04 PM   |  #2  
SimplicityApks's Avatar
Senior Member
Flag Aachen
Thanks Meter: 330
 
328 posts
Join Date:Joined: May 2013
Quote:
Originally Posted by mitsumei

I am requesting for a code that generates a random number from 0-100. for example it generates 55. then 55 won't be generated anymore unless the application exits or restarts.

Then just save all the generated numbers in a Set (or a boolean array or even in an ArrayList if you want to do more complex stuff with those numbers). Normally you don't have te right to request for code, but I'm in a good mood right now :

Code:
Select Code
private HashSet savedNumbers = new HashSet();

private int generateNewRandomNumber() {
   int number;
   do {
      number=(int) 101*Math.random();
   } while(savedNumbers.contains(number));
   savedNumbers.add(number);
   return number;
}
Last edited by SimplicityApks; 26th August 2014 at 09:13 AM.
26th August 2014, 01:28 AM   |  #3  
OP Junior Member
Thanks Meter: 0
 
2 posts
Join Date:Joined: Aug 2014
Quote:
Originally Posted by SimplicityApks

Then just save all the generated numbers in a Set (or a boolean array or even in an ArrayList<Integer> if you want to do more complex stuff with those numbers). Normally you don't have te right to request for code, but I'm in a good mood right now :

Code:
Select Code
private HashSet<Integer> savedNumbers = new HashSet<Integer>();

private int generateNewRandomNumber() {
   int number;
   do {
      number=(int) 101*Math.random();
   } while(savedNumbers.contains(number));
   return number;
}

thank you so much for the code but the generated numbers keeps on repeating.
i will generate random number from 0-4. but it keeps on repeating when i used your code
26th August 2014, 09:15 AM   |  #4  
SimplicityApks's Avatar
Senior Member
Flag Aachen
Thanks Meter: 330
 
328 posts
Join Date:Joined: May 2013
Quote:
Originally Posted by mitsumei

thank you so much for the code but the generated numbers keeps on repeating.
i will generate random number from 0-4. but it keeps on repeating when i used your code

Sorry forgot the statement: savedNumbers.add(number);
If you only generate from 0 of 4 it will crash on the sixth number in an endless loop
Last edited by SimplicityApks; 26th August 2014 at 08:46 PM.
27th August 2014, 12:23 AM   |  #5  
12er's Avatar
Member
Thanks Meter: 13
 
57 posts
Join Date:Joined: Aug 2014
I am describing two possible approaches: an online and an offline approach.
The online approach is pretty much the approach suggested above, and creates a new number whenever a new number is requested
Code:
Select Code
import java.util.HashSet;


public class RandSequence {
	
	private final int maxNum;
	private HashSet<Integer> alreadyUsed;
	
	/**
	 * Creates a RandSequence object.
	 * @param maxNum integers lower than maxNum will be created. maxNum must be greater than zero.
	 */
	public RandSequence(int maxNum) {
		this.maxNum = maxNum;
		this.alreadyUsed = new HashSet<Integer>();
	}
	
	/**
	 * Creates a random number, which has not been returned
	 * since the last reset, in the range [0,maxNum-1].
	 * @return a random number in the range of [0,maxNum-1]
	 * @throws Exception This Exception is thrown if maxNum numbers were returned.
	 */
	public int random() throws Exception {
		if(alreadyUsed.size() >= maxNum) {
			throw new Exception("Error: all integers in the range [0,maxNum-1] have already been returned");
		}
		int randNum = 0;
		do {
			randNum = (int)Math.floor(((double)maxNum) * Math.random());
		} while(alreadyUsed.contains(randNum));
		alreadyUsed.add(randNum);
		return randNum;
	}
	
	/**
	 * Call this method, if all random numbers have been used.
	 */
	public void reset() {
		alreadyUsed = new HashSet<Integer>();
	}

}
The very obvious downside: like for a coupon collector, it becomes harder and harder to find new items, when most items are used. The running time of the rand() method increases, and if maxNum calls are processed, a running time of at least c*maxNum^2 (c ... a certain constant amount of computation) is expected for the code above in all.

Here the following offline approach comes in: If a large fraction of the possible random numbers is expected to be created, it's much cheaper to create maxNum numbers, and permute them randomly, since maxNum commutations are necessary to create any permutation of maxNum items. Therefore creating all maxNum randnumbers at once like below is a lot cheaper if many random numbers are required:
Code:
Select Code
	/**
	 * Creates a non-repeating random sequence of maxNum integers in the range of [0,maxNum-1]
	 * @param maxNum length of the random sequence
	 * @return an array holding the permutations of the numbers
	 * @throws Exception An Exception is thrown if maxNum is nonpositive
	 */
	public static int[] permutations(int maxNum) throws Exception {
		if(maxNum < 1) {
			throw new Exception("Error: the number of random numbers must be positive");
		}
		int perm[] = new int[maxNum];
		for(int i=0 ; i<maxNum ; i++) {
			perm[i] = i;
		}
		
		//each permutation of n objects can be
		//achieved by executing n pairwise commutations
		for(int i=0 ; i<maxNum ; i++) {
			//pick randomly two elements of perm
			int i_1 = (int)Math.floor(((double)maxNum)*Math.random());
			int i_2 = (int)Math.floor(((double)maxNum)*Math.random());
			//then permute both elements of perm
			int first = perm[i_1];
			int second = perm[i_2];
			perm[i_1] = second;
			perm[i_2] = first;
		}
		
		return perm;
	}
The generated random numbers can now be consumed by iteratively walking through the returned array whenever random numbers are needed, until they are all used.
Suppose 1000 numbers of integers in [0,999] are created, this approach takes only 1000*c (c ... a certain constant amount of computation) computations, and in contrast the online approach may consume 500000*c computations. If we executed the for-loop for maxNum*2 times to really mix the numbers up well, using the offline approach would be still an advantage. But if only two or three of those random numbers are actually used, significantly more computations are required for the offline approach than for the online approach, and the memory requirements might also be a lot lower ... depending on the implementation of class HashSet (I haven't had a close look on the specs/source code of HashSet, but I suppose that the memory used for HashSet is expanded exponentially requiring a logarithmic number of reallocations with the number of items added to it).

Summary: use the first approach, if only few random numbers are used, use the second approach, if almost maxNum random numbers are required.
Last edited by 12er; 27th August 2014 at 01:18 AM.
The Following User Says Thank You to 12er For This Useful Post: [ View ]
Post Reply Subscribe to Thread
Previous Thread Next Thread
Thread Tools Search this Thread
Search this Thread:

Advanced Search
Display Modes


Top Threads in Java for Android App Development by ThreadRank