Results 1 to 16 of 16
Thread: Using random but once
 01202011, 09:28 PM #1Member
 Join Date
 Nov 2010
 Posts
 40
 Rep Power
 0
Using random but once
How would I use random numbers but only once.
For ex.
Java Code:int number = 0; Random thing = new Random(); while (number != 300){ number = thing.nextInt(5000); System.out.println(number) }
 01202011, 09:37 PM #2Senior Member
 Join Date
 Dec 2010
 Posts
 100
 Rep Power
 0
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,user0
 01202011, 10:25 PM #3Moderator
 Join Date
 Jul 2010
 Location
 California
 Posts
 1,641
 Rep Power
 7
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...
 01212011, 12:20 AM #4
Another alternative.
If the list of numbers is not too large then place them all in a List, shuffle, grab first number.
 01212011, 12:34 AM #5
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!Last edited by quad64bit; 01212011 at 02:46 AM. Reason: Correction
 01212011, 01:33 AM #6Member
 Join Date
 Nov 2010
 Posts
 40
 Rep Power
 0
Can someone please post a small example for a hash set if it's not to much trouble?
 01212011, 01:42 AM #7Senior Member
 Join Date
 Apr 2010
 Location
 Philippines
 Posts
 580
 Rep Power
 5
google is your friend.
Google
 01212011, 02:42 AM #8Java 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!
 01212011, 02:44 AM #9
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.
 01212011, 03:03 AM #10
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:
Java 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)); a.add(r); return r; } public int getF(){ int r; do { r = ran.nextInt(32767); } while (f[r] == true); f[r] = true; return r; } }
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.
 01212011, 06:13 AM #11Senior Member
 Join Date
 Mar 2010
 Posts
 952
 Rep Power
 5
I think Junky was talking about preloading and shuffling an array, not flagging. This was my instinct too, and it turns out to be the fastest.
Java 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)); a.add(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]}
My results:
Array: 15577
HashMap: 96
Flags: 27
Shuffle: 6
GaryLast edited by gcalvin; 01212011 at 06:27 AM. Reason: bad shuffle algorithm
 01212011, 06:19 AM #12
yeah whoops, I meant user0:
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.
 01212011, 06:26 AM #13
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.
 01212011, 06:31 AM #14Senior Member
 Join Date
 Mar 2010
 Posts
 952
 Rep Power
 5
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
 01212011, 07:01 AM #15
"If you know you are going to use all of the values exactly once each, then a shuffle is the way to go."
Agreed!
 01212011, 09:13 AM #16
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,881
 Blog Entries
 7
 Rep Power
 22
There's a break even point somewhere: if you want to generate m numbers out of a set [0,n) where m is near the value of m then a shuffle is ideal. If m is a lot smaller than n flagging the already generated numbers pays off (a BitSet is fine here) because generating all n numbers and shuffling them is quite a bit of overhead for just m < n numbers.
kind regards,
Joscenosillicaphobia: the fear for an empty beer glass
Similar Threads

Random
By Feilin in forum New To JavaReplies: 4Last Post: 08152010, 03:49 PM 
Random
By Arnold in forum New To JavaReplies: 13Last Post: 11142009, 11:53 AM 
how i use the random class to random the cards i have
By yanipao in forum New To JavaReplies: 14Last Post: 10192009, 10:57 AM 
How do I generate random numbers in a certain range using the random class?
By frasifrasi in forum New To JavaReplies: 8Last Post: 04192009, 05:50 PM 
random numbers without random class`
By carlos123 in forum New To JavaReplies: 4Last Post: 01172008, 11:44 PM
Bookmarks