Using random but once

• 01-20-2011, 09:28 PM
seanfmglobal
Using random but once
How would I use random numbers but only once.

For ex.
Code:

int number = 0;

Random thing = new Random();

while (number != 300){
number = thing.nextInt(5000);
System.out.println(number)
}

How would I get it to use a number then once used it will not be able to use the same digit again?
• 01-20-2011, 09:37 PM
user0
You could create an ArrayList of already generated random numbers, and every time a new number is generated, check to see if it is in the arraylist, if not, add it to the arraylist and use it for whatever it is you want, OR else if it already exists in the arraylistt, you can generate another random number.

Or you can create an array of booleans of the same size as your range, and every time a new number is generated, mark the corresponding index of the array as true, and use that to determine if a number has already been used.

That's how I would do it, I'm sure there are other ways.

Best,
• 01-20-2011, 10:25 PM
doWhile
To add to the post above, a HashSet might be more appropriate to than a List here, given its lookup is in constant time (relative to linear time for an ArrayList). For trivial situations the difference might not be noticable, but will be for more complex situations/loops/sizes/etc...
• 01-21-2011, 12:20 AM
Junky
Another alternative.

If the list of numbers is not too large then place them all in a List, shuffle, grab first number.
• 01-21-2011, 12:34 AM
I second Hashing -HashMaps have a linear access time for lookups, by far the most efficient method when you consider that they are both dynamic in size, and don't require initialization of empty values.

Edit:
Hash data structures have constant time performance, not linear - not sure why I said that!
• 01-21-2011, 01:33 AM
seanfmglobal
Can someone please post a small example for a hash set if it's not to much trouble?
• 01-21-2011, 01:42 AM
mine0926
• 01-21-2011, 02:42 AM
Code:

HashMap<Integer, Object> map = new HashMap<Integer, Object>();
//...
int r;
do{
r = random.nextInt();
}while(map.containsKey(r));
map.put(r, null);
//use r, its guaranteed to be unique now!

• 01-21-2011, 02:44 AM
Oh yeah, also FYI:
Hashtable and HashMap are more or less the same thing, but HashMap is newer and a bit faster (not thread safe), which should be fine for you. HashTable would work the same way.
• 01-21-2011, 03:03 AM
Hey, just for fun and out of curiosity, I wrote a quick and dirty empirical test of different methods, you guys might be interested in the methods/results. So, first the code, then my runtime results:
Code:

public class Misc {

public static void main(String[] args) {
new Misc();
}
Random ran = new Random();
HashMap<Integer, Object> m = new HashMap<Integer, Object>();
ArrayList<Integer> a = new ArrayList<Integer>();
boolean[] f = new boolean[32767];

public Misc() {
System.gc();
long start = System.currentTimeMillis();
for (int i= 0; i < 32767; i++) {
getA();
}
System.out.println("Array: "+(System.currentTimeMillis()-start));
System.gc();
start = System.currentTimeMillis();
for (int i= 0; i < 32767; i++) {
getM();
}
System.out.println("HashMap: "+(System.currentTimeMillis()-start));
System.gc();
start = System.currentTimeMillis();
for (int i= 0; i < 32767; i++) {
getF();
}
System.out.println("Flags: "+(System.currentTimeMillis()-start));
}

public int getM() {
int r;
do {
r = ran.nextInt(32767);
} while (m.containsKey(r));
m.put(r, null);
return r;
}

public int getA() {
int r;
do {
r = ran.nextInt(32767);
} while (a.contains(r));
return r;
}

public int getF(){
int r;
do {
r = ran.nextInt(32767);
} while (f[r] == true);
f[r] = true;
return r;
}
}

Results:
Array: 14851
HashMap: 74
Flags: 11

Conclusions:
The arraylist method is HORRIBLE. It must look through between 1 and N elements to find a match, 1/2N in the average case. The HashMap is Vastly improved, still less then 1/10 of a second for 32767 values. Flags (the technique Junky mentioned) is the fastest.

Keep in mind though, the flag technique requires two things:
None of your numbers can be fractional or negative (all positive integers)
- and it must be as large as your largest value.

For small sets, this method works well! For large sets and mixed number types (Real numbers [float/double], negative, extremely large [long]) it can be memory intensive. If I needed 1000 numbers between -999,999,999 and 999,999,999, then the flag method is a massive waste.
• 01-21-2011, 06:13 AM
gcalvin
I think Junky was talking about pre-loading and shuffling an array, not flagging. This was my instinct too, and it turns out to be the fastest.
Code:

[COLOR="Blue"]import java.util.ArrayList;
import java.util.HashMap;
import java.util.Random;
[/COLOR]
public class Misc {

public static void main(String[] args) {
new Misc();
}
[COLOR="Green"]private static final int MAX = 32767;[/COLOR]
Random ran = new Random();
HashMap<Integer, Object> m = new HashMap<Integer, Object>();
ArrayList<Integer> a = new ArrayList<Integer>();
boolean[] f = new boolean[[COLOR="Green"]MAX[/COLOR]];
[COLOR="Blue"]        int[] s = new int[[COLOR="Green"]MAX[/COLOR]];
int si = 0;
[/COLOR]
public Misc() {
System.gc();
long start = System.currentTimeMillis();
for (int i= 0; i < [COLOR="Green"]MAX[/COLOR]; i++) {
getA();
}
System.out.println("Array: "+(System.currentTimeMillis()-start));
System.gc();
start = System.currentTimeMillis();
for (int i= 0; i < [COLOR="Green"]MAX[/COLOR]; i++) {
getM();
}
System.out.println("HashMap: "+(System.currentTimeMillis()-start));
System.gc();
start = System.currentTimeMillis();
for (int i= 0; i < [COLOR="Green"]MAX[/COLOR]; i++) {
getF();
}
System.out.println("Flags: "+(System.currentTimeMillis()-start));
[COLOR="Blue"]                System.gc();
start = System.currentTimeMillis();
for (int i = 0; i < [COLOR="Green"]MAX[/COLOR]; i++) {
s[i] = i;
}
[COLOR="Green"]                // shuffle array
for (int i = MAX - 1; i > 0; i--) {
int pos = ran.nextInt(i);
int temp = s[i];
s[i] = s[pos];
s[pos] = temp;
}
[/COLOR]                for (int i = 0; i < [COLOR="Green"]MAX[/COLOR]; i++) {
getS();
}
System.out.println("Shuffle: "+(System.currentTimeMillis()-start));
[/COLOR]        }

public int getM() {
int r;
do {
r = ran.nextInt([COLOR="Green"]MAX[/COLOR]);
} while (m.containsKey(r));
m.put(r, null);
return r;
}

public int getA() {
int r;
do {
r = ran.nextInt([COLOR="Green"]MAX[/COLOR]);
} while (a.contains(r));
return r;
}

public int getF(){
int r;
do {
r = ran.nextInt([COLOR="Green"]MAX[/COLOR]);
} while (f[r] == true);
f[r] = true;
return r;
}
[COLOR="Blue"]
public int getS() {
return s[si++];
}
[/COLOR]}

I have edited my post because the code I posted included a bad shuffle algorithm.
My results:

Array: 15577
HashMap: 96
Flags: 27
Shuffle: 6

-Gary-
• 01-21-2011, 06:19 AM
yeah whoops, I meant user0:
Quote:

Or you can create an array of booleans of the same size as your range, and every time a new number is generated, mark the corresponding index of the array as true, and use that to determine if a number has already been used.
• 01-21-2011, 06:26 AM
Another solution is to repeatedly add to a HashMap or HashSet until the size of the set is the desired number of elements, and then return the set of keys. This is only slightly different than my previously described method, but allows the precomputation of all the values.
• 01-21-2011, 06:31 AM
gcalvin
I think hashing is helpful if you know you will use a small subset of the available values. If you know you are going to use all of the values exactly once each, then a shuffle is the way to go.

-Gary-
• 01-21-2011, 07:01 AM
"If you know you are going to use all of the values exactly once each, then a shuffle is the way to go."
Agreed!
• 01-21-2011, 09:13 AM
JosAH
Quote: