Dzielenie długich ciągów bez łamania słów wypełnianie wierszy

Question

Zanim pomyślicie, że jest on duplikowany (jest wiele pytań z pytaniem, jak podzielić długie ciągi bez łamania słów), należy pamiętać, że mój problem jest nieco inny: kolejność nie jest ważna, a ja Aby dopasować słowa, aby wykorzystać każdą linię tak bardzo, jak to możliwe.

Cześć,

Mam nieuporządkowana zestaw słów i chcę je połączyć bez użycia więcej niż 253 znaków.

Moim problemem jest to, że chcę spróbować wypełnić linię tak bardzo, jak to możliwe. Na przykład:

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) 

Jak mogę zrobić?

Answer 1

dla optymalny algorytm nieaktywny szybko 1D pakowania bin 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 

Wydajność

Przetestowane przez /usr/share/dict/words (dostarczone przez words-3.0-20.fc18.noarch) może to zrobić pół miliona słów w drugim na mój powolny dwurdzeniowy laptop o wydajności co najmniej 90% z tymi parametrami:

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

Z limit *= 1.5 Dostaję 92%, z limit *= 2 Dostaję 96% (ten sam czas wykonania).

Optymalna wartość (teoretyczna) oblicza się z: math.ceil(len(sep.join(words))/limit)

nie wydajny algorytm bin pakowania można zagwarantować zrobić lepsze

Źródło: http://mathworld.wolfram.com/Bin-PackingProblem.html

Morał z tej historii

Chociaż jest to interes Aby znaleźć najlepsze rozwiązanie, myślę, że w większości przypadków byłoby o wiele lepiej wykorzystać ten algorytm do rozwiązywania problemów z pakowaniem w trybie offline w trybie 1D.

Resources

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

Uwagi

• nie używałem odpychania tekstu dla mojego realizacji becau se jest wolniejszy niż mój prosty kod Pythona. Być może jest to związane z: Why are textwrap.wrap() and textwrap.fill() so slow?
• Wydaje się działać idealnie, nawet jeśli sortowanie nie jest odwrócone.

Answer 2

To jest bin packing problem; rozwiązanie jest NP-trudne, chociaż istnieją nieoptymalne algorytmy heurystyczne, głównie pierwsze dopasowanie zmniejszające i najlepiej pasujące malejące. Zobacz https://github.com/type/Bin-Packing dla implementacji.