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

Question

Мне нужно сгенерировать три строки текста (по сути, джиббериш), каждая из которых имеет длину 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. Вы должны думать о n-буквенном слове как о n + 1 букве, потому что каждое слово имеет либо пробел, либо возврат после него.
2. Поскольку все ваши слова имеют длину не менее 2 символов, вам никогда не захочется дойти до точки, где у вас будет заполнено 59 символов. Если вы наберете 57, вам нужно выбрать что-то 2письма плюс возврат.Если вы наберете 58, вам нужно 1-буквенное слово плюс возврат.
3. Вы пытаетесь оптимизировать время?Вы можете иметь одно и то же слово несколько раз?Несколько раз в одной строке?Имеет ли значение, если ваши слова распределены неравномерно, например, многие строки содержат «а» или «я», потому что это единственные однобуквенные слова в английском языке?

ВотОсновная идея.Для каждой строки начинайте выбирать длины слов и отслеживайте длину слов и общее количество символов.По мере приближения к концу строки выбирайте длину слова меньше, чем количество оставленных символов.(Например, если у вас осталось 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 

}