The best random “feel” integer generator for short sequences

Question

I am trying to figure out a way to create random numbers that “feel” random short short sequences. This is a quiz game where there are four possible options, and the software must choose one of four places where you can put the correct answer before filling in the other three with distractors.

It is obvious that arc4random % 4 will produce more than enough random results over a long sequence, but in a short sequence it is quite possible (and frequent occurrence!) To have five or six identical numbers in a row. This is what I try to avoid.

I also do not want to just say “never choose the same square twice”, because this leads to only three possible answers to each question, except the first. I am currently 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 for this that I miss?

Answer 1

If your question was how to calculate currentAnswer using your example probabilities without iterations, Guffa has your answer.

If the question is how to avoid random clustering without breaking the equiprobability, and you know the upper bound on the length of the list, then consider the following algorithm, which seems to be not 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 the actual working python code is purely random. I am sure that the previous probabilities are supported, and this seems like a cluster break (and sometimes adds some). But I'm pretty sleepy, so this only applies to entertainment.

Answer 2

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

So, in 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 3

To reduce the chance of a repeated number by 25%, you can choose a random number from 0 to 3.75, and then rotate it so that 0.75 ends with the previous answer.

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

Pseudocode (where / is integer division):

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

Answer 4

Set up a weighted array. Let's say the last value was 2. Create an array like this:

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

Then select the 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 possibilities P and weight 0<W<=1 use:

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

For P = 4 and W = 1/4 (P / WP (1-W)) = 13. This suggests that the latter value will be 1/4 more likely than others.

If you completely eliminate the most recent answer, it will be as noticeable as the most recent answer, which appears too often. I don’t know what weight will be right for you, but 1/4 is a good starting point.