分割長字符串，不破的話fullfilling線

Question

之前，你認爲它是重複的（也有很多問題，問如何分割長字符串不打破的話）採取記住，我的問題是有點不同：順序並不重要，我爲了儘可能多地使用每一行，我們已經適應了這些詞彙。

嗨，

我有一個無序的話，我想他們不使用超過253個字符組合。

def compose(words): 
    result = " ".join(words) 
    if len(result) > 253: 
     pass # this should not happen! 
    return result 

我的問題是，我想嘗試儘可能地填滿線。例如：

words = "a bc def ghil mno pq r st uv" 
limit = 5 # max 5 characters 

# This is good because it's the shortest possible list, 
# but I don't know how could I get it 
# Note: order is not important 
good = ["a def", "bc pq", "ghil", "mno r", "st uv"] 

# This is bad because len(bad) > len(good) 
# even if the limit of 5 characters is respected 
# This is equivalent to: 
# bad = ["a bc", "def", "ghil", "mno", "pq r", "st uv"] 
import textwrap 
bad = textwrap.wrap(words, limit) 

我該怎麼辦？

Answer 1

非最優的離線快速1D裝箱Python的算法

def binPackingFast(words, limit, sep=" "): 
    if max(map(len, words)) > limit: 
     raise ValueError("limit is too small") 
    words.sort(key=len, reverse=True) 
    res, part, others = [], words[0], words[1:] 
    for word in others: 
     if len(sep)+len(word) > limit-len(part): 
      res.append(part) 
      part = word 
     else: 
      part += sep+word 
    if part: 
     res.append(part) 
    return res 

性能

測試過/usr/share/dict/words（由words-3.0-20.fc18.noarch提供）它可以做在下半年萬字我慢雙核筆記本電腦，具有至少90％的那些參數的效率：

limit = max(map(len, words)) 
sep = "" 

隨着limit *= 1.5我得到92％，與limit *= 2我得到96％（相同的執行時間）。

優化（理論值）值與計算：math.ceil(len(sep.join(words))/limit)

沒有有效的裝箱算法可以保證做到更好

來源：​​

這個故事的寓意

雖然這是INTERES爲了找到最佳的解決方案，我認爲在大多數情況下，使用這種算法來處理一維離線bin裝箱問題要好得多。

資源

• ​​
• https://github.com/hudora/pyShipping/

注意

• 我沒有使用textwrap對我實施becau它比我簡單的Python代碼慢。 也許它與：Why are textwrap.wrap() and textwrap.fill() so slow?
• 它似乎工作完美，即使排序不顛倒。

Answer 2

這是bin packing problem;該解決方案是NP難的，儘管存在非最優的啓發式算法，主要是首先適合降低和最適合降低。有關實現，請參閱https://github.com/type/Bin-Packing。