1

我需要生成三行文本（基本上是乱码），每行 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]
            }
        }
    }
}
4

2 回答 2

1

  1. 您应该将 n 个字母的单词视为 n+1 个字母，因为每个单词后面都有一个空格或回车符。
  2. 由于您的所有单词都至少有 2 个字符长，因此您永远不想达到填写 59 个字符的程度。如果达到 57 个，您需要选择 2 个字母加上回车的内容。如果达到 58，则需要 1 个字母的单词加上 return。
  3. 您是否正在尝试优化时间？你可以多次使用同一个词吗？一行多次？如果您的单词分布不均匀，例如很多行包含“a”或“I”，因为它们是英语中唯一的单字母单词，这是否重要？

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

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

于 2010-03-01T15:55:09.577 回答
0 
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 

}
于 2010-03-01T16:05:29.150 回答