Generate Random Numbers Without Repetition

From CodeCodex

Implementations[edit]

C++[edit]

This is exactly the same as the java code below.

#include <iostream>
#include <map>
#include <algorithm>

using namespace std;

unsigned int rand_int(){
	unsigned int result=0;
	for(unsigned int i=0;i<sizeof(int);++i){
		result=(result<<8)+rand()%256;
	}
	return result;
}

int rand_range(int lower, int upper){  
	if(lower>upper){ // Swap if lower>upper  
		swap(lower,upper);
	}
	return rand_int()%(upper-lower+1)+lower;  
}

int GenerateRandomNumbers(int* result, int lower, int upper, int count){
	
	if(lower>upper){ // Swap if lower>upper
		swap(lower,upper);
	}
	
	if(count>upper-lower+1){ // It is impossible to generate the array
		return 0;
	}
	
	int diff=upper-lower;		
	
	for(int i=0;i<=count;++i){ // Initialize the array with the first numbers
		result[i]=i+lower;
	}
	
	map<int,int> number_map;
	
	for(int i=0;i<=count;++i){
		int index=rand_range(i,diff);
		if(index<=count){ // The index is in the array, so swap the items
			swap(result[i],result[index]);
		}
		else{
			map<int,int>::iterator it=number_map.find(index+lower);
			if(it!=number_map.end()){ // Lookup the number_map
				swap(it->second,result[i]);
			}
			else{
				number_map.insert(make_pair(index+lower,result[i])); // Add the item into the number_map
				result[i]=index+lower;
			}
		}
	}
	
	return count;
}

int main(){
	srand(time(0));
	int result[10];
	// Generate 10 random numbers within the range 1 to 100
	GenerateRandomNumbers(result,1,100,10);

	for(int i=0;i<10;++i)
		cout<<result[i]<<endl;
	return 0;
}

Sample output:

27
77
90
4
85
96
24
10
61
99

Java[edit]

Implementation 1[edit]

This function will return n number of random integers between 0 and maxRange, inclusive.

	public static final Random gen = new Random();
	public static int[] printRandomNumbers(int n, int maxRange) {
		assert n <= maxRange : "cannot get more unique numbers than the size of the range";
		
		int[] result = new int[n];
		Set<Integer> used = new HashSet<Integer>();
		
		for (int i = 0; i < n; i++) {
			
			int newRandom;
			do {
				newRandom = gen.nextInt(maxRange+1);
			} while (used.contains(newRandom));
			result[i] = newRandom;
			used.add(newRandom);
		}
		return result;
	}

This code is how you use the above function to print out the resulting number list:

	public static void main(String[] args) {
		
		for (int i : printRandomNumbers(10,100)) {
			System.out.println(i);
		}
		
	}

Here is an example output:

100
55
98
28
29
38
46
24
8
67

Implementation 2[edit]

This implementation does not require re-generating when the generated number is repeated. The complexity is O(n lg(n)) when using TreeMap and O(n) when using HashMap (n is independent of the range). The probability of each number is equal.

Random.java

package main;
import java.util.Map;
import java.util.HashMap;

public class Random {
	static java.util.Random random = new java.util.Random();
	// Generate a random integer N within the range lowerBound<=N<=upperBound
	static public int rand(int lowerBound, int upperBound){
		if(lowerBound>upperBound){ // Swap if lowerBound>upperBound
			int tmp=upperBound;
			upperBound=lowerBound;
			lowerBound=tmp;
		}
		return random.nextInt(upperBound-lowerBound+1)+lowerBound;
	}
	
	static public int[] GenerateRandomNumbers(int lowerBound, int upperBound, int count){
		if(lowerBound>upperBound){ // Swap if lowerBound>upperBound
			int tmp=upperBound;
			upperBound=lowerBound;
			lowerBound=tmp;
		}
		if(count>upperBound-lowerBound+1){ // It is impossible to generate the array
			return null;
		}
		
		int[] result = new int[count+1];
		int diff=upperBound-lowerBound;		
		
		for(int i=0;i<=count;++i){ // Initialize the array with the first numbers
			result[i]=i+lowerBound;
		}
		
		Map<Integer,Integer> map = new HashMap<Integer,Integer>();
		
		for(int i=0;i<=count;++i){
			int index=rand(i,diff);
			if(index<=count){ // The index is in the array, so swap the items
				int tmp=result[i];
				result[i]=result[index];
				result[index]=tmp;
			}
			else if(map.containsKey(index+lowerBound)){ // Lookup the map
				int tmp=map.get(index+lowerBound);
				map.put(index+lowerBound,result[i]);
				result[i]=tmp;
			}
			else{
				map.put(index+lowerBound,result[i]); // Add the item into the map
				result[i]=index+lowerBound;
			}
		}
		
		return result;
	}
}

Main.java

package main;
import main.Random;
public class Main {
	public static void main(String args[]){
		// Generate 10 distinct numbers ranging from 1 to 100
		int[] a=Random.GenerateRandomNumbers(1,100,10);
		for(int i=0;i<10;++i){
			System.out.println(a[i]);
		}
	}
}

Sample output:

21
38
18
60
44
2
77
81
78
51

Ruby[edit]

ary = (1..100).to_a
p ary.sample
p ary.sample(10)
p ary.sample(10)

Sample output:

38
[88, 59, 97, 54, 61, 48, 3, 7, 27, 74]
[4, 32, 9, 49, 54, 73, 13, 33, 11, 30]

WinBatch[edit]

 
;------------------------------------------------------------------------------------------------------------------------------------------
#DefineFunction udfItemListRandom (intLow, intHigh, strDelimiter)
strItemList = ""
intRange = intHigh - intLow
intCount = 1 + intRange
While ItemCount (strItemList, strDelimiter) < intCount
   intNum = intLow + Random (intRange)
   If !ItemLocate (intNum, strItemList, strDelimiter) Then strItemList = ItemInsert (intNum, -1, strItemList, strDelimiter)
EndWhile
Return strItemList
;..........................................................................................................................................
; This UDF udfItemListRandom creates an ItemList with (1 + intHigh - intLow) items
; of random value in the range from intLow to intHigh.
;..........................................................................................................................................
#EndFunction
;------------------------------------------------------------------------------------------------------------------------------------------

;------------------------------------------------------------------------------------------------------------------------------------------
#DefineFunction udfItemListRandomStep (intLow, intHigh, intStep, strDelimiter)
strItemList = ""
intCount = (intHigh - intLow) / Max (intStep, 1)
While ItemCount (strItemList, strDelimiter) <= intCount
   intNum = intLow + (intStep * (Random (intCount) mod (1 + intCount)))
   If !ItemLocate (intNum, strItemList, strDelimiter) Then strItemList = ItemInsert (intNum, -1, strItemList, strDelimiter)
EndWhile
Return strItemList
;..........................................................................................................................................
; This UDF udfItemListRandomStep creates an ItemList with (1 + ((intHigh - intLow) / intStep)) items
; of random value in the range from intLow to intHigh in stepwidth of intStep.
;..........................................................................................................................................
#EndFunction
;------------------------------------------------------------------------------------------------------------------------------------------


; Test.

strRandomList1 = udfItemListRandom (1, 6, ",")          ; 6 items e. g. "2,5,3,6,1,4"
strRandomList2 = udfItemListRandom (3, 11, ",")         ; 9 items e. g. "9,8,6,10,11,7,5,3,4"

strRandomList3 = udfItemListRandomStep (5, 25, 5, "|")  ; 5 items e. g. "5|25|10|20|15"
strRandomList4 = udfItemListRandomStep (5, 25, 3, "-")  ; 7 items e. g. "5-14-11-20-8-23-17"

Exit
; This WinBatch code example was written by Detlev Dalitz.20090723.2000.CEST