Simulate random iteration of array

Question

I have an array of given size. I want to traverse it in pseudorandom order, keeping array intact and visiting each element once. It will be best if current state can be stored in a few integers.

I know you can't have full randomness without storing full array, but I don't need the order to be really random. I need it to be perceived as random by user. The solution should use sub-linear space.

One possible suggestion - using large prime number - is given here. The problem with this solution is that there is an obvious fixed step (taken module array size). I would prefer a solution which is not so obviously non-random. Is there a better solution?

Answer 1

The idea of a random generator that simulates a shuffle is good if you can get one whose maximum period you can control.

A Linear Congruential Generator calculates a random number with the formula:

x[i + 1] = (a * x[i] + c) % m;

The maximum period is m and it is achieved when the following properties hold:

• The parameters c and m are relatively prime.
• For every prime number r dividing m, a - 1 is a multiple of r.
• If m is a multiple of 4 then also a - 1 is multiple of 4.

My first darft involved making m the next multiple of 4 after the array length and then finding suitable a and c values. This was (a) a lot of work and (b) yielded very obvious results sometimes.

I've rethought this approach. We can make m the smallest power of two that the array length will fit in. The only prime factor of m is then 2, which will make every odd number relatively prime to it. With the exception of 1 and 2, m will be divisible by 4, which means that we must make a - 1 a multiple of 4.

Having a greater m than the array length means that we must discard all values that are illegal array indices. This will happen at most every other turn and should be negligible.

The following code yields pseudo random numbers with a period of exaclty m. I've avoided trivial values for a and c and on my (not too numerous) spot cheks, the results looked okay. At least there was no obvious cycling pattern.

So:

class RandomIndexer
{
public:
    RandomIndexer(size_t length) : len(length)
    {
        m = 8;
        while (m < length) m <<= 1;

        c = m / 6 + uniform(5 * m / 6);
        c |= 1;

        a = m / 12 * uniform(m / 6);
        a = 4*a + 1;
        x = uniform(m);                      
    }

    size_t next()
    {
        do { x = (a*x + c) % m; } while (x >= len);

        return x;
    }

private:
    static size_t uniform(size_t m)
    {
        double p = std::rand() / (1.0 + RAND_MAX);

        return static_cast<int>(m * p);
    }

    size_t len;
    size_t x;
    size_t a;
    size_t c;
    size_t m;
};

You can then use the generator like this:

std::vector<int> list;
for (size_t i = 0; i < 3; i++) list.push_back(i);

RandomIndexer ix(list.size());
for (size_t i = 0; i < list.size(); i++) {
    std::cout << list[ix.next()]<< std::endl;
}

I am aware that this still isn't a great random number generator, but it is reasonably fast, doesn't require a copy of the array and seems to work okay.

If the approach of picking a and c randomly yields bad results, it might be a good idea to restrict the generator to some powers of two and to hard-code literature values that have proven to be good.

Answer 2

How about this algorithm?

To pseudo-pseudo randomly traverse an array of size n.

1. Create a small array of size k
2. Use the large prime number method to fill the small array, i = 0
3. Randomly remove a position using a RNG from the small array, i += 1
4. if i < n - k then add a new position using the large prime number method
5. if i < n goto 3.

the higher k is the more randomness you get. This approach will allow you to delay generating numbers from the prime number method.

A similar approach can be done to generate a number earlier than expected in the sequence by creating another array, "skip-list". Randomly pick items later in the sequence, use them to traverse the next position, and then add them to the skip-list. When they naturally arrive they are searched for in the skip-list and suppressed and then removed from the skip-list at which point you can randomly add another item to the skip-list.

Answer 3

As pointed out by others, you can create a sort of "flight plan" upfront by shuffling an array of array indices and then follow it. This violates the "it will be best if current state can be stored in a few integers" constraint but does it really matter? Are there tight performance constraints? After all, I believe that if you don't accept repetitions, than you need to store the items you already visited somewhere or somehow.

Alternatively, you can opt for an intrusive solution and store a bool inside each element of the array, telling you whether the element was already selected or not. This can be done in an almost clean way by employing inheritance (multiple as needed).
Many problems come with this solution, e.g. thread safety, and of course it violates the "keep the array intact" constraint.

Answer 4

Quadratic residues which you have mentioned ("using a large prime") are well-known, will work, and guarantee iterating each and every element exactly once (if that is required, but it seems that's not strictly the case?). Unluckily they are not "very random looking", and there are a few other requirements to the modulo in addition to being prime for it to work.
There is a page on Jeff Preshing's site which describes the technique in detail and suggests to feed the output of the residue generator into the generator again with a fixed offset.

However, since you said that you merely need "perceived as random by user", it seems that you might be able to do with feeding a hash function (say, cityhash or siphash) with consecutive integers. The output will be a "random" integer, and at least so far there will be a strict 1:1 mapping (since there are a lot more possible hash values than there are inputs).

Now the problem is that your array is most likely not that large, so you need to somehow reduce the range of these generated indices without generating duplicates (which is tough).

The obvious solution (taking the modulo) will not work, as it pretty much guarantees that you get a lot of duplicates.

Using a bitmask to limit the range to the next greater power of two should work without introducing bias, and discarding indices that are out of bounds (generating a new index) should work as well. Note that this needs non-deterministic time -- but the combination of these two should work reasonably well (a couple of tries at most) on the average.

Otherwise, the only solution that "really works" is shuffling an array of indices as pointed out by Kamil Kilolajczyk (though you don't want that).

Answer 5

Here is a java solution, which can be easily converted to C++ and similar to M Oehm's solution above, albeit with a different way of choosing LCG parameters.

import java.util.Enumeration;
import java.util.Random;

public class RandomPermuteIterator implements Enumeration<Long> {
    int c = 1013904223, a = 1664525;
    long seed, N, m, next;
    boolean hasNext = true;

    public RandomPermuteIterator(long N) throws Exception {
        if (N <= 0 || N > Math.pow(2, 62)) throw new Exception("Unsupported size: " + N);
        this.N = N;
        m = (long) Math.pow(2, Math.ceil(Math.log(N) / Math.log(2)));
        next = seed = new Random().nextInt((int) Math.min(N, Integer.MAX_VALUE));
    }

    public static void main(String[] args) throws Exception {
        RandomPermuteIterator r = new RandomPermuteIterator(100);
        while (r.hasMoreElements()) System.out.print(r.nextElement() + " ");
        //output:50 52 3 6 45 40 26 49 92 11 80 2 4 19 86 61 65 44 27 62 5 32 82 9 84 35 38 77 72 7 ...
    }

    @Override
    public boolean hasMoreElements() {
        return hasNext;
    }

    @Override
    public Long nextElement() {
        next = (a * next + c) % m;
        while (next >= N) next = (a * next + c) % m;
        if (next == seed) hasNext = false;
        return  next;
    }
}

Answer 6

maybe you could use this one: http://www.cplusplus.com/reference/algorithm/random_shuffle/ ?