как использовать случайные биты для моделирования 26-сторонней ярмарки, умирают?

Наивная реализация заключалась бы в объединении случайных битов для получения десятичного или целочисленного значения с использованием фиксированного числа битов (скажем, 4 байта для получения целого числа). Разделите результат на максимально возможное значение количества предоставленных битов, что, я думаю, должно дать вам десятичную дробь, равномерно распределенную в диапазоне 0-1. (По сути, это функция rand ()). Затем выполните 26 * rand ()

Основной ответ здесь кажется правильным - если ваше случайное число 0..32 больше 25, перебросьте. Тем не менее, вы можете сложить шансы против произвольно длинного результата, ища множитель 26, что дает меньшие шансы на открытие длинной позиции.

 32 -  26 =  6
 64 -  52 =  12
128 -  78 =  50

... и так далее. Я собрал скрипт Python, чтобы вычислить наилучшее доступное количество бит до 32, для хихиканья, и получил такой результат:

2^13 - 26 * 315 = 2
2^14 - 26 * 630 = 4

Так что в любом случае у вас есть 1 из 2 ^ 12 шансов на повторное прокручивание, если вы используете 13 или 14 бит.Ваш алгоритм в этом случае будет:

def random_character():
    r = 8190
    while r >= 8190:
        r = rand(13) # assuming rand generates an N bit integer
    return chr(r % 26 + ord('a'))

РЕДАКТИРОВАТЬ: Из любопытства я сравнил эти шансы с несколькими важными значениями, чтобы увидеть, действительно ли 13 было оптимальным числом (при условии, что вы можете сгенерировать любое количество битов, от 1 до 32, за то же время - если вы не можете, 13 бит лучше всего). Основываясь на моей (правда, сонной) математике, если вы можете получить 32 бита так же дешево, как 16, сделайте это. В противном случае используйте 13.

2^8 through 2^12: by definition, no better than 1/2^12 odds
2^16: diff is 16, so 1/2^11
2^17: diff is 6, so slightly under 1/2^14
2^18: diff is 12, so slightly under 1/2^12
2^19: diff is 24, so slightly under 1/2^14
2^20: diff is 22, so slightly under 1/2^15
2^21: diff is 18, so slightly under 1/2^16
2^22: diff is 10, so slightly under 1/2^18
2^23: diff is 20, so slightly under 1/2^18
2^24: diff is 14, so slightly under 1/2^20
2^25: diff is 2, so 1/2^24
2^26: diff is 4, so 1/2^24
2^27: diff is 8, so 1/2^24
2^28: diff is 16, so 1/2^24
2^29: diff is 6, so slightly under 1/2^26
2^30: diff is 12, so slightly under 1/2^26
2^31: diff is 24, so slightly under 1/2^26
2^32: diff is 22, so slightly under 1/2^27

26 - это 11010 в двоичном формате.
Сгенерируйте пять битов, если они превышают 26, либо:

1. Верните значение по модулю 26 (предпочтение будет отдано меньшим значениям)
2. Отбросьте результат и перейдите снова (Имеет возможность никогда не закончиться)

Или обобщите его:
Сгенерировать (войти в базу 2) + 1 бит. Если они превышают n, вернуть значение по модулю n или отбросить и снова перейти.

Самый простой подход в вашем случае - выбросить 5 бит, что дает 32 (0–31) равновероятных результатов. Если вы получите значение за пределами вашего диапазона (больше 25), попробуйте еще раз (и снова ...)

Среднее количество «монет» (битов), которые нужно бросить в этом случае для каждой буквы, будет

 5 x 32 / 26  = 6.15

( Для справки см. геометрическое распределение )

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

Простой алгоритм заключается в выборе случайного числа от 0 до следующего по величине числа вида 2 ^ n - 1 (31 в данном случае). Если число, которое вы случайно выбрали, слишком велико, отбросьте его и снова выбирайте, пока не получите число в пределах допустимого диапазона.

Очевидно, что это не оптимальный алгоритм, поскольку вы «тратите впустую» некоторую информацию, но его должно хватить для большинства целей. Наиболее расточительно, если количество сторон матрицы чуть больше 2 мкм для некоторого м , например: 33 стороны. В этом случае вам придется отбрасывать значение почти в 50% случаев.