Results 1 to 16 of 16
  1. #1
    seanfmglobal is offline Member
    Join Date
    Nov 2010
    Posts
    40
    Rep Power
    0

    Default 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)
    }
    How would I get it to use a number then once used it will not be able to use the same digit again?

  2. #2
    user0 is offline Senior Member
    Join Date
    Dec 2010
    Posts
    100
    Rep Power
    0

    Default

    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--

  3. #3
    doWhile is offline Moderator
    Join Date
    Jul 2010
    Location
    California
    Posts
    1,641
    Rep Power
    7

    Default

    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...

  4. #4
    Junky's Avatar
    Junky is offline Grand Poobah
    Join Date
    Jan 2011
    Location
    Dystopia
    Posts
    3,798
    Rep Power
    7

    Default

    Another alternative.

    If the list of numbers is not too large then place them all in a List, shuffle, grab first number.

  5. #5
    quad64bit's Avatar
    quad64bit is offline Moderator
    Join Date
    Jul 2009
    Location
    VA
    Posts
    1,323
    Rep Power
    7

    Default

    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; 01-21-2011 at 01:46 AM. Reason: Correction

  6. #6
    seanfmglobal is offline Member
    Join Date
    Nov 2010
    Posts
    40
    Rep Power
    0

    Default

    Can someone please post a small example for a hash set if it's not to much trouble?

  7. #7
    mine0926 is offline Senior Member
    Join Date
    Apr 2010
    Location
    Philippines
    Posts
    580
    Rep Power
    5

    Default

    google is your friend.
    Google

  8. #8
    quad64bit's Avatar
    quad64bit is offline Moderator
    Join Date
    Jul 2009
    Location
    VA
    Posts
    1,323
    Rep Power
    7

    Default

    Java 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!

  9. #9
    quad64bit's Avatar
    quad64bit is offline Moderator
    Join Date
    Jul 2009
    Location
    VA
    Posts
    1,323
    Rep Power
    7

    Default

    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.

  10. #10
    quad64bit's Avatar
    quad64bit is offline Moderator
    Join Date
    Jul 2009
    Location
    VA
    Posts
    1,323
    Rep Power
    7

    Default

    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;
        }
    }
    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.

  11. #11
    gcalvin is offline Senior Member
    Join Date
    Mar 2010
    Posts
    953
    Rep Power
    5

    Default

    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.
    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]}
    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-
    Last edited by gcalvin; 01-21-2011 at 05:27 AM. Reason: bad shuffle algorithm

  12. #12
    quad64bit's Avatar
    quad64bit is offline Moderator
    Join Date
    Jul 2009
    Location
    VA
    Posts
    1,323
    Rep Power
    7

    Default

    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.

  13. #13
    quad64bit's Avatar
    quad64bit is offline Moderator
    Join Date
    Jul 2009
    Location
    VA
    Posts
    1,323
    Rep Power
    7

    Default

    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.

  14. #14
    gcalvin is offline Senior Member
    Join Date
    Mar 2010
    Posts
    953
    Rep Power
    5

    Default

    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-

  15. #15
    quad64bit's Avatar
    quad64bit is offline Moderator
    Join Date
    Jul 2009
    Location
    VA
    Posts
    1,323
    Rep Power
    7

    Default

    "If you know you are going to use all of the values exactly once each, then a shuffle is the way to go."
    Agreed!

  16. #16
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,654
    Blog Entries
    7
    Rep Power
    21

    Default

    Quote Originally Posted by quad64bit View Post
    "If you know you are going to use all of the values exactly once each, then a shuffle is the way to go."
    Agreed!
    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,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

Similar Threads

  1. Random
    By Feilin in forum New To Java
    Replies: 4
    Last Post: 08-15-2010, 03:49 PM
  2. Random
    By Arnold in forum New To Java
    Replies: 13
    Last Post: 11-14-2009, 10:53 AM
  3. Replies: 14
    Last Post: 10-19-2009, 10:57 AM
  4. Replies: 8
    Last Post: 04-19-2009, 05:50 PM
  5. random numbers without random class`
    By carlos123 in forum New To Java
    Replies: 4
    Last Post: 01-17-2008, 10:44 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •