如何從單詞詞典中生成給定長度的隨機文本行（bin-packing問題）？

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個字符長，所以你永遠不會想要達到59個字符填充的點。如果你到了57，你需要選擇2個字母加上返回。如果你達到58，你需要一個1個字母的單詞加上返回。
2. 您是否試圖優化時間？你可以多次使用同一個單詞嗎？一行多次？如果你的單詞不是均勻分佈的，例如很多行包含「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 

}