拆分长串而不会破坏满足线条的单词

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

这是垃圾箱包装问题 ; 解决方案是NP难的,尽管存在非最优启发式算法,主要是先适合递减和最佳拟合递减.有关实现,请参阅https://github.com/type/Bin-Packing.

Answer 2

非最优离线快速一维装箱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），它可以在我的慢速双核笔记本电脑上每秒处理 50 万个单词，使用这些参数时效率至少为 90%：

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

我得到limit *= 1.5了 92%，limit *= 2我得到了 96%（相同的执行时间）。

最佳（理论）值的计算公式为：math.ceil(len(sep.join(words))/limit)

没有有效的装箱算法可以保证做得更好

资料来源： http: //mathworld.wolfram.com/Bin-PackingProblem.html

故事的道德启示

虽然找到最佳解决方案很有趣，但我认为在大多数情况下，使用此算法来解决一维离线装箱问题会更好。

资源

• http://mathworld.wolfram.com/Bin-PackingProblem.html
• https://github.com/hudora/pyShipping/

笔记

• 我没有使用 textwrap 来实现，因为它比我的简单 Python 代码慢。也许与以下内容有关：为什么 textwrap.wrap() 和 textwrap.fill() 这么慢？
• 即使排序不颠倒，它似乎也能完美工作。