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

Ответ 1

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

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

Ответ 2

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

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

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

Я использую 27 в приведенном выше коде, так как общее пространство выборки для выбора строк из "ab" - это 26 1-символьных возможностей и 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 больше или равно sampspace - range [14 - 8 = 6]. Другими словами, для значений от 6 до 13 включительно 8 из 14 возможностей.

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

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

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

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

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

Ответ 3

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

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;
}

Ответ 4

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

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

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

<?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);
}

Ответ 5

Изменить: этот ответ не совсем прав. См. Нижнюю часть для защиты. Я оставлю это сейчас в надежде, что кто-то может придумать вариант, который его исправляет.

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

Доказательство того, что это правильно, немного жестко, и я не уверен, что я доверяю своим раскрывающимся полномочиям, чтобы дать понять, но неся со мной. В целях объяснения мы генерируем строки длиной не более 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 ^th строки мы сначала попытаемся сгенерировать символы после k. Если наш рекурсивный вызов возвращает что-либо, то мы знаем, что строка должна быть как минимум длиной k, и мы генерируем собственный символ из алфавита и возвращаем его. Если, однако, рекурсивный вызов ничего не возвращает, мы знаем, что строка не больше, чем k, и мы используем описанную выше процедуру для выбора либо конечного символа, либо символа no. Здесь реализация этого в 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)

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

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

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

Изменить: Disproof, предоставленный другом:

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 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

Ответ 6

// 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;
}

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

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

Ответ 7

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

Скажем, ваш алфавит имеет символы 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.

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

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

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

RandomStringGenerator класс

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 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%.

Ответ 8

Моя идея относительно этого:

у вас есть длина строки длиной 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. Теперь это число лежит между 0-3, так что идите 1 строку длины или если случайная выбранный номер равен 7, затем перейдите к строке с двойной длиной.

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

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

Спасибо и посмотрим Mawia

Ответ 9

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