長い文字列を分割せずに完全な文字列を分割する

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 

パフォーマンス

（words-3.0-20.fc18.noarch提供）/usr/share/dict/words上でテストされた、それは私の遅い上の第2の内半分万語を行うことができますデュアルコアラップトップは、これらのパラメータで少なくとも90％の効率を持ちます：

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

limit *= 1.5と私は92％を得て、limit *= 2と私は96％（同じ実行時間）を得る。

最適（理論）値を用いて算出される：​​

物語のモラル：math.ceil(len(sep.join(words))/limit)

全く効率的なビンパッキングアルゴリズムは、より良い

出典を行うことを保証することはできません

それはinteres最良の解決策を見つけようと思えば、ほとんどの場合、このアルゴリズムを1Dオフラインビンのパッキング問題に使用するほうがずっと良いと思います。

リソース

• ​​
• 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を参照してください。