Как генерировать случайные строки текста определенной длины из словаря слов (проблема с упаковкой)?

Question

Мне нужно сгенерировать три строки текста (по существу, jibberish) длиной 60 символов, включая жесткий возврат в конце каждой строки. Строки создаются из словаря слов различной длины (обычно 1-8 символов). Ни одно слово не может использоваться более одного раза, а слова должны быть разделены пробелами. Я думаю, что это, по сути, проблема с упаковкой.

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

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

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

dictionary // map of words with word lengths as keys and arrays of corresponding words as values 
lengths // array of word lengths, sorted numerically 
min = lengths[0] // minimum word length 
max = lengths[lengths.length - 1] // maximum word length 
line = "" 
while (line.length < 60) { 
    len = lengths[round(rand() * (lengths.length - 1))] 
    if (dictionary[len] != null && dictionary[len].length > 0) { 
     diff = 60 - line.length // number of characters needed to complete the line 

     if (line.length + len + 1 == 60) { 
      // this word will complete the line exactly 
      line += dictionary[len].splice(0, 1) + "\n" 
     } 
     else if (min + max + 2 >= diff) { 
      // find the two word lengths that will complete the line 
      // ==> this is where I'm having trouble 
     } 
     else if (line.length + len + 1 < 60 - max) { 
      // this word will fit safely, so just add it 
      line += dictionary[len].splice(0, 1) + " " 
     } 

     if (dictionary[len].length == 0) { 
      // delete any empty arrays and update min and max lengths accordingly 
      dictionary[len] = null 
      delete dictionary[len] 

      i = lengths.indexOf(len) 
      if (i >= 0) { 
       // words of this length have been depleted, so 
       // update lengths array to ensure that next random 
       // length is valid 
       lengths.splice(i, 1) 
      } 
      if (lengths.indexOf(min) == -1) { 
       // update the min 
       min = lengths[0] 
      } 
      if (lengths.indexOf(max) == -1) { 
       // update the max 
       max = lengths[lengths.length - 1] 
      } 
     } 
    } 
} 

Answer 1

1. Вы должны думать о п буквах слова как являющийся п +-буквы, потому что каждое слово имеет либо пробел, либо вернуться после него.
2. Поскольку все ваши слова имеют длину не менее 2 символов, вы никогда не захотите попасть туда, где у вас есть 59 символов. Если вы добираетесь до 57, вам нужно выбрать что-то, что составляет 2 буквы плюс вернуть. Если вы добираетесь до 58, вам нужно 1-буквенное слово плюс возвращение.
3. Вы пытаетесь оптимизировать время? Можете ли вы иметь одно и то же слово несколько раз? Несколько раз в одной строке? Имеет ли значение, если ваши слова не распределены равномерно, например. много строк содержат «a» или «I», потому что это единственные однобуквенные слова на английском языке?

Вот основная идея. Для каждой строки начинайте выбирать длину слов и отслеживайте длины слов и общее количество символов. Когда вы приближаетесь к концу строки, выберите длину слова меньше, чем количество оставшихся символов. (например, если у вас осталось 5 символов, выберите слова в диапазоне от 2 до 5 символов, считая пробел.) Если вы получите до 57 символов, выберите 3-буквенное слово (счетчик возврата). Если вы получите до 58 символов, выберите двухбуквенное слово (счетчик возврата).

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

Answer 2

dictionnary = Group your words by lengths (like you already do) 
total_length = 0 
phrase = "" 

while (total_length < 60){ 

random_length = generate_random_number(1,8) 

if (total_length + random_length > 60) 
{ 
    random_length = 60 - total_length // possibly - 1 if you cound \n and -2 if you 
            // append a blank anyway at the end 
} 

phrase += dictionnary.get_random_word_of_length(random_length) + " " 
total_length += random_length + 1 

}