Разделение длинной строки без разрыва слов строк полного заполнения

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 

Performance

Испытано над /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)

не эффективный алгоритм бен-упаковки не может быть гарантировано, чтобы сделать лучше

Источник: http://mathworld.wolfram.com/Bin-PackingProblem.html

Мораль истории

Пока это интересно ting, чтобы найти лучшее решение, я думаю, что в большинстве случаев было бы гораздо лучше использовать этот алгоритм для проблем с упаковкой 1D автономного буфера.

Ресурсы

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

Примечания

• Я не использовал TextWrap для моей реализации becau se это медленнее, чем мой простой код Python. Возможно, это связано с: Why are textwrap.wrap() and textwrap.fill() so slow?
• Кажется, что он отлично работает, даже если сортировка не отменена.

Answer 2

Это bin packing problem; решение является NP-жестким, хотя существуют неоптимальные эвристические алгоритмы, в основном сходящиеся снижаются и лучше всего подходят для уменьшения. См. https://github.com/type/Bin-Packing для реализаций.