Non-Repeating Random Number Generator in Java

Question

I am trying to create a subclass of the Random class in Java that does not repeat its output, and here is what I've got so far ..

import java.util.Set;
import java.util.concurrent.CopyOnWriteArraySet;

public class NonRepetitiveRandom extends java.util.Random {
    private Set<Integer> noUseInts = new CopyOnWriteArraySet<Integer>();
    private static final long serialVersionUID = 1L;

    @Override
    protected int next(int bits) {
        int i;
        for (i = super.next(bits); noUseInts.contains(i); i = super.next(bits))
            ;
        noUseInts.add(i);
        return i;
    }
}

Is it fine ? Do I need to add anything ? I initially tried overriding each next* method using the same model as above, but after noticing that the next method itself is used in all next* methods, I am trying to override it alone.

Note: The shuffling method will not work, because it creates a whole list and shuffles it every time a value is demanded. Also, it wouldn't be practical if ranges are wide and if no ranges are specified at all. In fact, the only use case for this method is when I already have a list at hand. As a conclusion, a non-repeating random number generator would be the most practical solution.

is it fine in what way? This is a crazy requirement to begin with. — MK., May 27 '15 at 17:05
Possible [duplicate](http://stackoverflow.com/q/8115722/230513). — trashgod, May 27 '15 at 17:09
You could write it in a more concise and (I think) more readable way: `int next; while(!noUseInts.add(next = super.next(bits))); return next;`. Also CopyOnWriteArraySet will become quite slow as it grows (add/contains are O(n))... — assylias, May 27 '15 at 17:10
@SotiriosDelimanolis, Well, that would naturally be expected. — Amr Ayman, May 27 '15 at 17:10
@trashgod that does not really work if you have an unlimited number of items.... — assylias, May 27 '15 at 17:10
@assylias: Agree; the `java.util.Random` period is [finite](http://stackoverflow.com/q/6463443/230513). — trashgod, May 27 '15 at 17:13
The question is whether this requirement is just contrived (school or job interview assignment) or is it the result of a real situation, in which case perhaps you should explain the situation, so we may offer alternatives. — RealSkeptic, May 27 '15 at 17:27
@AmrAyman This may be more efficient: `Collections.newSetFromMap(new ConcurrentHashMap<>()));` — assylias, May 27 '15 at 17:36
@RealSkeptic: I am creating a limited number of instances of a class where certain properties must not exist more than once. The number of these properties is more than the number of instances and should be chosen randomly. — Amr Ayman, May 27 '15 at 17:37
Then you should prepare a list of possible properties, and then shuffle it, and just take the next property from the shuffled list when you create your instances. If you want more in-depth explanation, you should expand your question and add the actual problem and the code of the way you're doing it now. — RealSkeptic, May 27 '15 at 17:41
@RealSkeptic: I guess that'd be more suited. My approach was to have a non repeating random number sequence __manually__ shuffle the list for me. — Amr Ayman, May 27 '15 at 17:49
Sounds like you want [`Collections.shuffle()`](http://docs.oracle.com/javase/8/docs/api/java/util/Collections.html#shuffle-java.util.List-) — pjs, May 27 '15 at 18:09
After checking it, shuffling won't work because other classes will be demanding selection out of ranges of values. So, creating a list of all possible values (especially if the ranges are large), shuffling it and selecting the first would be performance expensive. With that in mind, a non-repeating random number generator would be most suitable as it generates only one number on the fly and doesn't create a whole list of values. Note that this functionality will be called for a lot in the code. — Amr Ayman, May 27 '15 at 18:58

score 0 · Answer 1 · answered May 27 '15 at 17:14

It looks like your code will produce the output you want. If you plan to use it for many many generations of random numbers however, the parameter space you have to search to find the next random number will keep decreasing. Naively, it will take longer to generate the next random number each time on average, so beware of this if you are generating many many numbers.

Non-Repeating Random Number Generator in Java

1 Answers1