Редактировать: Этот ответ не совсем правильный.Смотрите внизу для опровержения.Я оставлю это пока в надежде, что кто-то может придумать вариант, который это исправляет.
Это можно сделать без отдельного расчета длины, что, как отмечали другие,требует увеличения числа до большой степени, и, как правило, мне кажется, что это грязное решение.
Доказать, что это правильно, немного сложно, и я не уверен, что доверяю своим объяснительным силам, чтобы прояснить это, но терпеть меня.В целях объяснения мы генерируем строки длиной не более n из алфавита a из |a| символов.
Во-первых, представьте, что у вас максимальная длина n,и вы уже решили, что генерируете строку по крайней мере n-1.Должно быть очевидно, что есть |a|+1 одинаково вероятные возможности: мы можем сгенерировать любой из |a| символов из алфавита, или мы можем выбрать для завершения n-1 символов.Чтобы решить, мы просто выбираем случайное число x между 0 и |a| (включительно);если x равно |a|, мы заканчиваем n-1 символами;в противном случае мы добавляем символ x th в строку.Вот простая реализация этой процедуры в Python:
def pick_character(alphabet):
x = random.randrange(len(alphabet) + 1)
if x == len(alphabet):
return ''
else:
return alphabet[x]
Теперь мы можем применить это рекурсивно.Чтобы сгенерировать символ строки k th , мы сначала попытаемся сгенерировать символы после k.Если наш рекурсивный вызов что-либо возвращает, мы знаем, что строка должна быть длиной не менее 1031 *, и мы генерируем собственный символ из алфавита и возвращаем его.Однако, если рекурсивный вызов ничего не возвращает, мы знаем, что строка не длиннее k, и мы используем вышеприведенную процедуру для выбора либо последнего символа, либо никакого символа.Вот реализация этого в Python:
def uniform_random_string(alphabet, max_len):
if max_len == 1:
return pick_character(alphabet)
suffix = uniform_random_string(alphabet, max_len - 1)
if suffix:
# String contains characters after ours
return random.choice(alphabet) + suffix
else:
# String contains no characters after our own
return pick_character(alphabet)
Если вы сомневаетесь в единообразии этой функции, вы можете попытаться опровергнуть ее: предложите строку, для которой есть два различных способа ее генерации, или ни одного.Если таких строк нет - и, увы, у меня нет веских доказательств этого факта, хотя я вполне уверен, что это правда - и, учитывая, что отдельные выборки одинаковы, в результате также должна быть выбрана любая строка с одинаковой вероятностью.
Как и было обещано, и в отличие от любого другого решения, опубликованного до сих пор, повышение чисел до крупных держав не требуется;для хранения результата не требуется целых чисел произвольной длины или чисел с плавающей запятой, и достоверность, по крайней мере, на мой взгляд, довольно легко продемонстрировать.Это также короче, чем любое полностью указанное решение.;)
Если кто-то захочет добавить надежное доказательство единообразия функции, я был бы чрезвычайно признателен.
Редактировать: Отказ, предоставленный другом:
dato: so imagine alphabet = 'abc' and n = 2
dato: you have 9 strings of length 2, 3 of length 1, 1 of length 0
dato: that's 13 in total
dato: so probability of getting a length 2 string should be 9/13
dato: and probability of getting a length 1 or a length 0 should be 4/13
dato: now if you call uniform_random_string('abc', 2)
dato: that transforms itself into a call to uniform_random_string('abc', 1)
dato: which is an uniform distribution over ['a', 'b', 'c', '']
dato: the first three of those yield all the 2 length strings
dato: and the latter produce all the 1 length strings and the empty strings
dato: but 0.75 > 9/13
dato: and 0.25 < 4/13