Random iteration over an array using divide and conquer

Question

I have created a utility class which allows random iteration over an array. The idea is pretty much a divide and conquer approach.

public class RandomIterator<T> implements Iterator<T> {

    //recursion stack
    private final LinkedList<int[]> offsets = new LinkedList<>();
    private final ThreadLocalRandom random = ThreadLocalRandom.current();
    private final T[] words;

    public RandomIterator(T[] words) {

        this.words = words;

        //add default lower and upper bound
        offsets.addLast(new int[]{0, words.length});
    }

    @Override
    public boolean hasNext() {
        return !offsets.isEmpty();
    }

    @Override
    public T next() {

        final int[] offset = offsets.removeFirst();

        final int upperBound = offset[1];
        final int lowerBound = offset[0];

        final T toReturn;

        if (lowerBound + 1 == upperBound) {

            //range contains only 1 index
            toReturn = words[lowerBound];
        } else {

            final int randomIndex = random.nextInt(lowerBound, upperBound);
            toReturn = words[randomIndex];

            if (randomIndex + 1 < upperBound)
                offsets.addLast(new int[]{randomIndex + 1, upperBound});
            if (randomIndex > lowerBound)
                offsets.addLast(new int[]{lowerBound, randomIndex});
        }

        return toReturn;
    }
}

You can see this in action here. It works fine, but I feel its not truly random. The original array used in the link above is a lexicographically sorted array of 2000 latin words. As we can see in the output there are multiple groups of words which appear to be in order. For e.g.. a range like this occurred in one run.

aberam
abeas
abditi
abdidimusque
abdideris
abdiderim
abdideras
abdideramus
abalienato

Suggestions will be much appreciated :)

EDIT

It seems I did not express my thoughts properly. I do not want repetitions during the random iteration. The idea is basically to cover all the array indices once, but do it randomly. The example linked above does this. It uses the same lexicographically sorted array of latin words on each run, and randomly iterates it and writes out each word to the outputstream. Randomness in the output can be defined as probability of occurrence of words with very small "distance" from each other. For eg. the words "quote" and "quoted" have very small distance. My requirement is that word with very small distance should not occur close to each other in the output (random).

When I say the output is not truly random, I mean that I can observe groups of contiguous words in the output which have very small distance from each other. Hence the output gives the expression of not being truly random.

Answer 1

Bug?

    private final ThreadLocalRandom random = ThreadLocalRandom.current();

This doesn't look right. What happens if your current thread copies your object and spawns a new thread? It will copy the current random instance.

When you use it

            final int randomIndex = random.nextInt(lowerBound, upperBound);

You should instead say

            final int randomIndex = ThreadLocalRandom.current().nextInt(lowerBound, upperBound);

That way, even if your object exists in multiple threads, each one will access a separate instance of ThreadLocalRandom.

Your current implementation may return the same random result multiple times, which would give the "non-random" appearance that you're seeing.

Note that if you are using an old version of Java, there was apparently a bug that could cause this to happen even when called correctly.

Answer 2

Just to close the question. Divide and conquer is not a good approach for the problem. I made a much simpler implementation and it is working fine.

The idea is to keep a linked list of indexes and randomly remove them. We get random indexes and avoid repetition. Although we have to create this linked list every time we want to iterate, something which I wanted to avoid in the first place, but it seems like a pre mature optimisation hence going ahead with this only.

@Override
public T next() {

    final int index = offsets.remove(getRandomIndex());
    return words[index];
}