Как я генерирую случайную строку до определенной длины?

Вместо того чтобы выбирать длину с равномерным распределением, взвесьте ее в зависимости от того, сколько строк имеют заданную длину. Если ваш алфавит имеет размер m, то существует m^x строк размера x, и (1-mⁿ⁺¹)/(1-m) строк длины n или меньше. Вероятность выбора строки длины x должна быть m^x*(1-m)/(1-mⁿ⁺¹).

Edit:

Что касается переполнения - использование плавающей точки вместо целых чисел расширит диапазон, поэтому для 26-символьного алфавита и плавающих чисел одинарной точности прямое вычисление веса не должно переполняться при n<26.

Более надежный подход - решать эту проблему итеративно. Это также должно минимизировать эффект переполнения:

int randomLength() {
  for(int i = n; i > 0; i--) {
    double d = Math.random();
    if(d > (m - 1) / (m - Math.pow(m, -i))) {
      return i;
    }
  }
  return 0;
}

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

int randomLength() {
  for(int i = n; i > 0; i -= 5) {
    double d = Math.random();
    double c = (m - 1) / (m - Math.pow(m, -i))
    for(int j = 0; j < 5; j++) {
      if(d > c) {
        return i - j;
      }
      c /= m;
    }
  }
  for(int i = n % 0; i > 0; i--) {
    double d = Math.random();
    if(d > (m - 1) / (m - Math.pow(m, -i))) {
      return i;
    }
  }
  return 0;
}

Что вам нужно сделать, так это сгенерировать длину, а затем строку как два отдельных шага. Сначала нужно выбрать длину, используя взвешенный подход. Вы можете рассчитать количество строк заданной длины l для алфавита из k символов как k^l. Просуммируйте их, и вы получите общее количество строк любой длины, первым шагом будет генерация случайного числа от 1 до этого значения и его соответствующая сортировка. Отклоняясь по модулю на одну ошибку, вы будете разбивать на 26, 26^2, 26^3, 26^4 и так далее. Логарифм, основанный на количестве символов, будет полезен для этой задачи.

Как только вы получили длину, вы можете генерировать строку, как описано выше.

Хорошо, есть 26 вариантов для строки из 1 символа, 26 ² для строки из 2 символов и так далее до 26 ²⁶ вариантов для строки из 26 символов. нить.

Это означает, что существует в 26 раз больше возможностей для (N) -символьной строки, чем для (N-1) -символьной строки. Вы можете использовать этот факт для выбора длины:

def getlen(maxlen):
    sz = maxlen
    while sz != 1:
        if rnd(27) != 1:
            return sz
        sz--;
    return 1

Я использую 27 в приведенном выше коде, так как общее пространство выборки для выбора строк из «ab» составляет 26 вариантов с одним символом и 26 ² 2 возможности персонажа. Другими словами, соотношение составляет 1:26, поэтому вероятность для 1 символа составляет 1/27 (а не 1/26, как я сначала ответил).

Это решение не идеальное , поскольку вы вызываете rnd несколько раз, и было бы лучше вызвать его один раз с возможным диапазоном 26 ^N +26 ^N-1 +26 ¹ и выберите длину в зависимости от того, где находится возвращаемое вами число, но может быть сложно найти генератор случайных чисел, который будет работать на такие большие числа (10 символов дают вам возможный диапазон 26 ¹⁰ + ... + 26 ¹ , что, если я не ошибся с математикой, составляет 146 813 779 479 510).

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

def getlen(chars,maxlen):
    assert maxlen >= 1
    range = chars
    sampspace = 0
    for i in 1 .. maxlen:
        sampspace = sampspace + range
        range = range * chars
    range = range / chars
    val = rnd(sampspace)
    sz = maxlen
    while val < sampspace - range:
        sampspace = sampspace - range
        range = range / chars
        sz = sz - 1
    return sz

Как только у вас будет длина, я буду использовать ваш текущий алгоритм чтобы выбрать фактические символы для заполнения строки.

Объясняя это дальше:

Допустим, наш алфавит состоит только из «ab».Возможные наборы до длины 3: [ab] (2), [ab] [ab] (4) и [ab] [ab] [ab] (8). Таким образом, есть 8/14 шансов получить длину 3, 4/14 длины 2 и 2/14 длины 1.

14 - это магическая цифра: это сумма всех 2 ⁿ для n = 1 до максимальной длины. Итак, тестирование этого псевдокода выше с chars = 2 и maxlen = 3 :

    assert maxlen >= 1 [okay]
    range = chars [2]
    sampspace = 0
    for i in 1 .. 3:
        i = 1:
            sampspace = sampspace + range [0 + 2 = 2]
            range = range * chars [2 * 2 = 4]
        i = 2:
            sampspace = sampspace + range [2 + 4 = 6]
            range = range * chars [4 * 2 = 8]
        i = 3:
            sampspace = sampspace + range [6 + 8 = 14]
            range = range * chars [8 * 2 = 16]
    range = range / chars [16 / 2 = 8]
    val = rnd(sampspace) [number from 0 to 13 inclusive]
    sz = maxlen [3]
    while val < sampspace - range: [see below]
        sampspace = sampspace - range
        range = range / chars
        sz = sz - 1
    return sz

Итак, из этого кода первая итерация последнего цикла завершится с sz = 3 , если val больше или равно samppace - range [14 - 8 = 6] . Другими словами, для значений с 6 по 13 включительно 8 из 14 возможностей.

В противном случае samppace становится samppace - range [14 - 8 = 6] , а range становится range / chars [8/2 = 4 ] .

Затем вторая итерация последнего цикла завершится с sz = 2 , если val больше или равно samppace - range [6 - 4 = 2] . Другими словами, для значений от 2 до 5 включительно 4 из 14 возможных.

В противном случае samppace становится samppace - range [6 - 4 = 2] , а range становится range / chars [4/2 = 2] ] .

Затем третья итерация последнего цикла завершится с sz = 1 , если val больше или равно samppace - range [2 - 2 = 0] .Другими словами, для значений от 0 до 1 включительно, 2 из 14 возможностей (эта итерация будет всегда завершаться, поскольку значение должно быть больше или равно нулю.

Оглядываясь назад, это второе решение По моему личному мнению, я бы выбрал первое решение из-за его простоты и во избежание возможности получения довольно больших чисел.

Редактировать: Этот ответ не совсем верен. Опровержение см. внизу. Я оставлю его пока в надежде, что кто-нибудь придумает вариант, который его исправит.

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

Доказать, что это верно, довольно сложно, и я не уверен, что доверяю своим способностям изложения, чтобы сделать это ясным, но потерпите. Для целей объяснения мы генерируем строки длиной не более n из алфавита a из |a| символов.

Сначала представьте, что у вас есть максимальная длина n, и вы уже решили, что генерируете строку по крайней мере длины n-1. Должно быть очевидно, что существует |a|+1 равновероятных возможностей: мы можем сгенерировать любой из |a| символов алфавита, или мы можем выбрать завершение на n-1 символах. Чтобы решить, мы просто выбираем случайное число x между 0 и |a| (включительно); если x равно |a|, мы завершаем на n-1 символах; в противном случае мы добавляем x^th символ a к строке. Вот простая реализация этой процедуры в Python:

def pick_character(alphabet):
  x = random.randrange(len(alphabet) + 1)
  if x == len(alphabet):
    return ''
  else:
    return alphabet[x]

Теперь мы можем применить ее рекурсивно. Чтобы сгенерировать k^-й символ строки, мы сначала попытаемся сгенерировать символы после k. Если наш рекурсивный вызов возвращает что-либо, то мы знаем, что строка должна быть длиной не менее k, и мы генерируем собственный символ из алфавита и возвращаем его. Если же рекурсивный вызов ничего не возвращает, мы знаем, что длина строки не превышает 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)

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

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

Если кто-нибудь захочет помочь с надежным доказательством однородности функции, я буду очень благодарен.

Edit: Disproof, provided by a friend:

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

// Note space as an available char
alphabet = "abcdefghijklmnopqrstuvwxyz "

result_string = ""

for( ;; )
{
    s = ""

    for( i = 0; i < n; i++ )
        s += alphabet[rand(0, 26)]

    first_space = n;

    for( i = 0; i < n; i++ )
        if( s[ i ] == ' ' )
        {
            first_space = i;
            break;
        }

    ok = true;

    // Reject "duplicate" shorter strings
    for( i = first_space + 1; i < n; i++ )
        if( s[ i ] != ' ' )
        {
            ok = false;
            break;
        }

    if( !ok )
        continue;

    // Extract the short version of the string
    for( i = 0; i < first_space; i++ )
        result_string += s[ i ];

    break;
}

Изменить: я забыл запретить строки нулевой длины, это займет немного больше кода, который у меня сейчас нет времени добавлять.

Изменить: после рассмотрения того, как мой ответ не масштабируется до большого n (слишком много времени, чтобы получить удачу и найти принятую строку), мне гораздо больше нравится ответ paxdiablo. И меньше кода.

Матье: Ваша идея не работает, потому что строки с пробелами по-прежнему с большей вероятностью будут сгенерированы. В вашем случае с n = 4 вы можете создать строку 'ab' как 'a' + 'b' + '' + '' или '' + 'a' + 'b' + '' или другие комбинации . Таким образом, не все струны имеют одинаковые шансы на появление.

Моя идея по этому поводу такая:

у вас есть строка длиной 1 n. Там 26 возможных строк 1 длины, 26 * 26 строк длины 2 и так далее. вы можете узнать процент каждой строки длины от общего количества возможных строк. например, процент строки одиночной длины имеет вид

((26 / (TOTAL_POSSIBLE_STRINGS_OF_ALL_LENGTH)) * 100).

аналогично вы можете узнать процентное соотношение строк другой длины. Отметьте их на числовой строке от 1 до 100. Т.е. предположим, что процент строки одинарной длины равен 3, а строка двойной длины - 6, тогда строка одинарной длины числовой строки находится между 0-3, а строка двойной длины находится между 3-9 и так далее. Теперь возьмите случайное число от 1 до 100. Найдите диапазон, в котором это число находится. Я имею в виду, что, например, предположим, что число, которое вы выбрали случайным образом, равно 2. выбрано число 7, затем выберите строку двойной длины.

Таким образом, вы можете видеть, что длина каждой выбранной строки будет пропорциональна проценту от общего числа строк этой длины, вносимых во все возможные строки.

Надеюсь, я ясен. Отказ от ответственности: я не рассматривал вышеуказанное решение, кроме одного или двух, поэтому, если оно совпадает с каким-то одним решением, это будет чисто случайным. Кроме того, я буду приветствовать все советы и положительную критику и поправлю меня, если я ошибаюсь.

Благодарность и уважение Мавиа

Основываясь на моем комментарии, опубликованном в качестве ответа на OP:

Я бы посчитал это упражнением на базе превращение. Вы просто генерируете "случайное число" в "основании 26", где a=0 и z=25. Для случайной строки length n, сгенерировать число между 1 и 26^н. Преобразование из базы 10 в базу 26, используя символы из выбранного вами алфавит.

Вот реализация PHP. Я не буду с гарантией, что здесь нет ошибки off-by-one или двух, но любая такая ошибка должна быть незначительной:

<?php
$n = 5;

var_dump(randstr($n));

function randstr($maxlen) {
        $dict = 'abcdefghijklmnopqrstuvwxyz';
        $rand = rand(0, pow(strlen($dict), $maxlen));
        $str = base_convert($rand, 10, 26);
        //base convert returns base 26 using 0-9 and 15 letters a-p(?)
        //we must convert those to our own set of symbols
        return strtr($str, '1234567890abcdefghijklmnopqrstuvwxyz', $dict);
}

Лично я бы сделал это так:

Допустим, в вашем алфавите Z символов. Тогда количество возможных строк для каждой длины L будет:

L | Z
--------------------------
1 | 26
2 | 676 (= 26 * 26)
3 | 17576 (= 26 * 26 * 26)

... и так далее.

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

(1 - (Z ^ (N + 1))) / (1 - Z) 

Назовем это значение S . Тогда вероятность генерации строки любой длины L должна быть:

(Z ^ L) / S

Хорошо, хорошо. Это все хорошо; но как нам сгенерировать случайное число с учетом неравномерного распределения вероятностей?

Короткий ответ: вы этого не делаете. Получите библиотеку, которая сделает это за вас. Я разрабатываю в основном на .NET, поэтому я мог бы обратиться к Math.NET .

Тем не менее, это действительно не , поэтому сложно придумать элементарный подход к тому, чтобы сделать это самостоятельно.

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

Вот пример на C # одного из способов реализации этой идеи (прокрутите вниз, например, вывод):

RandomStringGenerator class

public class RandomStringGenerator
{
    private readonly Random _random;
    private readonly char[] _alphabet;

    public RandomStringGenerator(string alphabet)
    {
        if (string.IsNullOrEmpty(alphabet))
            throw new ArgumentException("alphabet");

        _random = new Random();
        _alphabet = alphabet.Distinct().ToArray();
    }

    public string NextString(int maxLength)
    {
        // Get a value randomly distributed between 0.0 and 1.0 --
        // this is approximately what the System.Random class provides.
        double value = _random.NextDouble();

        // This is where the magic happens: we "translate" the above number
        // to a length based on our computed probability distribution for the given
        // alphabet and the desired maximum string length.
        int length = GetLengthFromRandomValue(value, _alphabet.Length, maxLength);

        // The rest is easy: allocate a char array of the length determined above...
        char[] chars = new char[length];

        // ...populate it with a bunch of random values from the alphabet...
        for (int i = 0; i < length; ++i)
        {
            chars[i] = _alphabet[_random.Next(0, _alphabet.Length)];
        }

        // ...and return a newly constructed string.
        return new string(chars);
    }

    static int GetLengthFromRandomValue(double value, int alphabetSize, int maxLength)
    {
        // Looping really might not be the smartest way to do this,
        // but it's the most obvious way that immediately springs to my mind.
        for (int length = 1; length <= maxLength; ++length)
        {
            Range r = GetRangeForLength(length, alphabetSize, maxLength);
            if (r.Contains(value))
                return length;
        }

        return maxLength;
    }

    static Range GetRangeForLength(int length, int alphabetSize, int maxLength)
    {
        int L = length;
        int Z = alphabetSize;
        int N = maxLength;

        double possibleStrings = (1 - (Math.Pow(Z, N + 1)) / (1 - Z));
        double stringsOfGivenLength = Math.Pow(Z, L);
        double possibleSmallerStrings = (1 - Math.Pow(Z, L)) / (1 - Z);

        double probabilityOfGivenLength = ((double)stringsOfGivenLength / possibleStrings);
        double probabilityOfShorterLength = ((double)possibleSmallerStrings / possibleStrings);

        double startPoint = probabilityOfShorterLength;
        double endPoint = probabilityOfShorterLength + probabilityOfGivenLength;

        return new Range(startPoint, endPoint);
    }
}

Range struct

public struct Range
{
    public readonly double StartPoint;
    public readonly double EndPoint;

    public Range(double startPoint, double endPoint)
        : this()
    {
        this.StartPoint = startPoint;
        this.EndPoint = endPoint;
    }

    public bool Contains(double value)
    {
        return this.StartPoint <= value && value <= this.EndPoint;
    }
}

Test

static void Main(string[] args)
{
    const int N = 5;
    const string alphabet = "acegikmoqstvwy";
    int Z = alphabet.Length;

    var rand = new RandomStringGenerator(alphabet);

    var strings = new List<string>();
    for (int i = 0; i < 100000; ++i)
    {
        strings.Add(rand.NextString(N));
    }

    Console.WriteLine("First 10 results:");
    for (int i = 0; i < 10; ++i)
    {
        Console.WriteLine(strings[i]);
    }

    // sanity check
    double sumOfProbabilities = 0.0;

    for (int i = 1; i <= N; ++i)
    {
        double probability = Math.Pow(Z, i) / ((1 - (Math.Pow(Z, N + 1))) / (1 - Z));
        int numStrings = strings.Count(str => str.Length == i);

        Console.WriteLine("# strings of length {0}: {1} (probability = {2:0.00%})", i, numStrings, probability);

        sumOfProbabilities += probability;
    }

    Console.WriteLine("Probabilities sum to {0:0.00%}.", sumOfProbabilities);

    Console.ReadLine();
}

Вывод :

First 10 results:
wmkyw
qqowc
ackai
tokmo
eeiyw
cakgg
vceec
qwqyq
aiomt
qkyav
# strings of length 1: 1 (probability = 0.00%)
# strings of length 2: 38 (probability = 0.03%)
# strings of length 3: 475 (probability = 0.47%)
# strings of length 4: 6633 (probability = 6.63%)
# strings of length 5: 92853 (probability = 92.86%)
Probabilities sum to 100.00%.