分割长字符串，不破的话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。