Random number

[Joey Alencar]

Hi, I'd like to get a random number, but without repetition. How can I do this?
Thanks.

[David Weitzman]

You want to insure that the same number does not show up twice? Try something like this:

java.util.TreeSet set = new java.util.TreeSet();
java.util.Random r = new java.util.Random();
public int getRandomInt() {
  while (true) {
    int potential = r.nextInt();
    Integer i = new Integer(potential);
    if (!set.contains(i)) {
      set.add(i);
      return potential;
    }
  }
}

[Ken Manohar]

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.

[Dirk Schreckmann]

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

[Thomas Paul]

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]

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]

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]

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]

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?

[Elouise Kivineva]

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]

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.