如何从单词词典中生成给定长度的随机文本行（装箱问题）？

Question

我需要生成三行文本（本质上是胡言乱语），每行长度为 60 个字符，包括每行末尾的硬回车。这些行是根据不同长度（通常为 1-8 个字符）的单词词典生成的。任何单词不得使用多次，并且单词之间必须用空格分隔。我认为这本质上是一个装箱问题。

到目前为止我采取的方法是创建单词的 hashMap，并按其长度分组。然后，我选择一个随机长度，从地图中提取该长度的单词，并将其附加到我当前生成的行的末尾，考虑空格或硬回车。它大约有一半的时间有效，但另一半的时间我陷入无限循环并且我的程序崩溃。

我遇到的一个问题是：当我向行中添加随机单词时，给定长度的单词组可能会耗尽。这是因为字典中每个长度的单词数量不一定相同，例如，可能只有一个长度为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. 您是否正在尝试优化时间？同一个词可以出现多次吗？一行中多次？如果您的单词分布不均匀，例如很多行包含“a”或“I”，因为这些是英语中唯一的单字母单词，这有什么关系吗？

这是基本想法。对于每一行，开始选择单词长度，并跟踪到目前为止的单词长度和总字符数。当您接近行尾时，选择的单词长度小于剩余的字符数。 （例如，如果还剩 5 个字符，请选择 2-5 个字符范围内的单词，计算空格。）如果达到 57 个字符，请选择一个 3 个字母的单词（计算回车）。如果达到 58 个字符，请选择一个 2 个字母的单词（计算返回值）。

如果需要，您可以在此时打乱单词长度，这样所有行都不会以短单词结尾。然后对于每个单词长度，选择一个该长度的单词并将其插入。

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 

}