Лучший генератор случайных целочисленных значений для коротких последовательностей - PullRequest
Новая
       10

Лучший генератор случайных целочисленных значений для коротких последовательностей

4 голосов
/ 23 июня 2010

Я пытаюсь найти способ создания случайных чисел, которые «кажутся» случайными на коротких последовательностях.Это для игры-викторины, где есть четыре возможных варианта, и программное обеспечение должно выбрать одно из четырех мест, в котором нужно поставить правильный ответ, прежде чем заполнить остальные три с помощью отвлекающих факторов.

Очевидно, arc4random % 4 создаст более чем достаточно случайные результаты в длинной последовательности, но в короткой последовательности вполне возможно (и часто встречается!), Чтобы пять или шесть одинаковых чисел возвращались подряд.Это то, чего я хочу избежать.

Я также не хочу просто говорить «никогда не выбирайте один и тот же квадрат дважды», потому что это дает только три возможных ответа на каждый вопрос, кроме первого.В настоящее время я делаю что-то вроде этого: 

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

Есть ли лучшее решение, которое я пропускаю?

Ответы [ 4 ]

3 голосов
/ 23 июня 2010

Если ваш вопрос состоял в том, как вычислить currentAnswer, используя вероятности вашего примера не итеративно, у Guffa есть ваш ответ.

Если вопрос заключается в том, как избежать случайной кластеризации, не нарушая равновероятности, и вы знаете верхнюю границу длины списка, то рассмотрите следующий алгоритм, который как бы не сортирует: 

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

, где любое отношение к фактическому рабочему коду Python является чисто случайным. Я почти уверен, что априорные вероятности сохраняются, и кажется, что они разбивают кластеры (и иногда добавляют некоторые). Но я очень сонный, так что это только для развлечения.

3 голосов
/ 23 июня 2010

Вы заполняете массив результатов, затем shuffle , затем присваиваете их в этом порядке.

Итак, всего 8 вопросов: 

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

shuffle(answer_slots)

print answer_slots
 [1,3,2,1,0,2,3,0]
0 голосов
/ 23 июня 2010

Настройка взвешенного массива. Допустим, последнее значение было 2. Создайте массив следующим образом: 

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

Затем выберите число в массиве. 

newValue = array[arc4random() % 13];

Теперь перейдите к использованию математики вместо массива. 

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

Для P возможностей и веса 0<W<=1 используйте: 

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

Для P = 4 и W = 1/4, (P / W-P (1-W)) = 13. Это говорит о том, что последнее значение будет на 1/4 вероятнее, чем другие значения.

Если вы полностью исключите самый последний ответ, он будет так же заметен, как и самый последний ответ, появляющийся слишком часто. Я не знаю, какой вес вам подойдет, но 1/4 - хорошая отправная точка.

0 голосов
/ 23 июня 2010

Чтобы уменьшить вероятность повторения числа на 25%, вы можете выбрать случайное число от 0 до 3,75, а затем повернуть его так, чтобы 0,75 оказалось в предыдущем ответе.

Чтобы избежать использования значений с плавающей запятой, вы можете умножить коэффициенты на четыре:

Псевдокод (где / - целочисленное деление): 

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