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.