• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Random number

 
Ranch Hand
Posts: 43
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi, I'd like to get a random number, but without repetition. How can I do this?
Thanks.
 
Ranch Hand
Posts: 1365
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
You want to insure that the same number does not show up twice? Try something like this:
 
Greenhorn
Posts: 4
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
The Math class in java.lang (I think, don't worry it is imported automatically) has a class (static) method called random(), which returns a random decimal value between 0 and 1.
If you want you use this method but get a random number instead you have to 'cast it' e.g.
int randomNumber = (int) Math.random() * 10;
The variable randomNumber will produce a number lying between 0 and 9 inclusive.
 
Sheriff
Posts: 7023
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Originally posted by Ken Manohar:
int randomNumber = (int) Math.random() * 10;
The variable randomNumber will produce a number lying between 0 and 9 inclusive.


Almost...
Actually, what you've suggested will produce the number 0 - every single time.
(int)(Math.random() * 10) is probably what you were thinking...
 
mister krabs
Posts: 13974
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Imagine a case where you want to generate all the numbers from 1 to 1,000,000 in a random order. If you simply generate random numbers and then check to see if they have already been selected, you might possibly run for a very long time.
I ran using the tree option to generate random numbers from 1 to 1,000,000 and it hung. For numbers from 1 to 100,000 it ran for 4 seconds.
So depending on the range of numbers, the Tree option may be practical.
 
David Weitzman
Ranch Hand
Posts: 1365
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thomas Paul: I am watching your every move
If you want to hit every number in a range it may be easiest to put them all in an ArrayList (pre-allocated to the right size of course) and use Collections.shuffle() (there's a method something like that). Is that any faster Paul?
Or try it again with a HashSet, since you know the hash values for integers will have a good distribution.
What if you stick all the numbers in a TreeSet to begin with and remove them as you find them (instead of adding them as you go along).
What if you had a LinkedList which you repeatedly iterated, ignoring random numbers of iterations and taking the current item as your value and calling Iterator.remove()?
Maybe you should really do it yourself with a custom binary search and the int[] type instead of a List of Integers, to save the time wasted on indirection. Use some magic number like -1 instead of setting things to null or removing them.
Or perhaps you could just fake random numbers by XORing a simple sequence with some random bits.
I'm going to stop now before I get myself hurt.
 
Thomas Paul
mister krabs
Posts: 13974
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thomas Paul: I am watching your every move
Should I be worried?
If you want to hit every number in a range it may be easiest to put them all in an ArrayList (pre-allocated to the right size of course) and use Collections.shuffle() (there's a method something like that). Is that any faster Paul?
I couldn't find a method anything like that.
What if you stick all the numbers in a TreeSet to begin with and remove them as you find them (instead of adding them as you go along).
I thought of that. It took about 2X longer.
Maybe you should really do it yourself with a custom binary search and the int[] type instead of a List of Integers, to save the time wasted on indirection. Use some magic number like -1 instead of setting things to null or removing them.

I wrote a customized IntList. You can't set items to a magic number because you need to get them out of the list so that you don't pick them over and over again. Remember, a list with 1,000,000 entries will eventually have only 1 valid entry left so you don't want to poke around the list hitting all those entries that contain the magic number.
I got 100,000 entries down to 10 seconds. 200,000 entries took 83 seconds. 1,000,000 entries still hangs.
The problem is that as the number of entries increases, removing items from the array becomes more and more expensive.
I'm going to put this out as a challenge in the Advanced forum.
 
Dirk Schreckmann
Sheriff
Posts: 7023
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Originally posted by David Weitzman:
Maybe you should really do it yourself with a custom binary search and the int[] type instead of a List of Integers, to save the time wasted on indirection. Use some magic number like -1 instead of setting things to null or removing them.


I tried it this way. I got 1,000,000 reps down to 13 to 17 seconds and 10,000,000 reps down to 180 to 190 seconds. (By no means do I pretend to be an efficiency expert - or beginner.)
Should anybody figure out a fast/efficient way of doing this (maybe 100,000,000 in under a minute), I'd be curious to learn what you figured out.
Good Luck.
 
Thomas Paul
mister krabs
Posts: 13974
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Originally posted by Dirk Schreckmann:

I tried it this way. I got 1,000,000 reps down to 13 to 17 seconds and 10,000,000 reps down to 180 to 190 seconds. (By no means do I pretend to be an efficiency expert - or beginner.)
Should anybody figure out a fast/efficient way of doing this (maybe 100,000,000 in under a minute), I'd be curious to learn what you figured out.
Good Luck.



Could you show the code?
 
Ranch Hand
Posts: 155
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Here's how to use that Collections.shuffle() idea:
You start with a table where your numbers are stored in order as either ints or Strings:
String numbers[]= new String[size];
Then create a List object from your table:
List list = Arrays.asList( numbers );
Next use Collections class'es static method shuffle. It takes a List object and shuffles the values at its indexes:
Collections.shuffle( List );
To see what you've got at a given index:
list.get(i).toString()
 
David Weitzman
Ranch Hand
Posts: 1365
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thomas, I wasn't addressing you. I was quoting you (it the same sort of idea as in this article)
Ok, what if you ... never mind -- file access is slow.
I'll wait until I get home and check out the pseudorandom number generation methods in Applied Cryptography. If you returned the state of the generator or a simple function of the state, you can probably get a bunch of different numbers.
 
reply
    Bookmark Topic Watch Topic
  • New Topic