Better random "feeling" integer generator for short sequences

Question

I'm trying to figure out a way to create random numbers that "feel" random over short sequences. This is for a quiz game, where there are four possible choices, and the software needs to pick one of the four spots in which to put the correct answer before filling in the other three with distractors.

Obviously, arc4random % 4 will create more than sufficiently random results over a long sequence, but in a short sequence its entirely possible (and a frequent occurrence!) to have five or six of the same number come back in a row. This is what I'm aiming to avoid.

I also don't want to simply say "never pick the same square twice," because that results in only three possible answers for every question but the first. Currently I'm doing something like this:

bool acceptable = NO;
do {
  currentAnswer = arc4random() % 4;
  if (currentAnswer == lastAnswer) {
    if (arc4random() % 4 == 0) {
      acceptable = YES;
    }
  } else {
    acceptable = YES;
  }
} while (!acceptable);

Is there a better solution to this that I'm overlooking?

Answer 1

To reduce the probability for a repeated number by 25%, you can pick a random number between 0 and 3.75, and then rotate it so that the 0.75 ends up at the previous answer.

To avoid using floating point values, you can multiply the factors by four:

Pseudo code (where / is an integer division):

currentAnswer = ((random(0..14) + lastAnswer * 4) % 16) / 4

Answer 2

Set up a weighted array. Lets say the last value was a 2. Make an array like this:

array = [0,0,0,0,1,1,1,1,2,3,3,3,3];

Then pick a number in the array.

newValue = array[arc4random() % 13];

Now switch to using math instead of an array.

newValue = ( ( ( arc4random() % 13 ) / 4 ) + 1 + oldValue ) % 4;

For P possibilities and a weight 0<W<=1 use:

newValue = ( ( ( arc4random() % (P/W-P(1-W)) ) * W ) + 1 + oldValue ) % P;

For P=4 and W=1/4, (P/W-P(1-W)) = 13. This says the last value will be 1/4 as likely as other values.

If you completely eliminate the most recent answer it will be just as noticeable as the most recent answer showing up too often. I do not know what weight will feel right to you, but 1/4 is a good starting point.

Answer 3

You populate an array of outcomes, then shuffle it, then assign them in that order.

So for just 8 questions:

answer_slots = [0,0,1,1,2,2,3,3]

shuffle(answer_slots)

print answer_slots
 [1,3,2,1,0,2,3,0]

Answer 4

If your question was how to compute currentAnswer using your example's probabilities non-iteratively, Guffa has your answer.

If the question is how to avoid random-clustering without violating equiprobability and you know the upper bound of the length of the list, then consider the following algorithm which is kind of like un-sorting:

from random import randrange
# randrange(a, b) yields a <= N < b

def decluster():
    for i in range(seq_len):
        j = (i + 1) % seq_len
        if seq[i] == seq[j]:
            i_swap = randrange(i, seq_len) # is best lower bound 0, i, j?
            if seq[j] != seq[i_swap]:
                print 'swap', j, i_swap, (seq[j], seq[i_swap])
                seq[j], seq[i_swap] = seq[i_swap], seq[j]

seq_len = 20
seq = [randrange(1, 5) for _ in range(seq_len)]; print seq
decluster(); print seq
decluster(); print seq

where any relation to actual working Python code is purely coincidental. I'm pretty sure the prior-probabilities are maintained, and it does seem break clusters (and occasionally adds some). But I'm pretty sleepy so this is for amusement purposes only.