Suddivisione di stringhe lunghe senza rotture di parole righe di riempimento

Question

Prima di pensare che sia duplicato (ci sono molte domande che chiedono come suddividere le stringhe lunghe senza rompere le parole) tenere presente che il mio problema è un po 'diverso: l'ordine non è importante e io 'Adattare le parole per usare ogni riga il più possibile.

Ciao,

Ho un insieme non ordinato di parole e voglio combinarli senza utilizzare più di 253 caratteri.

def compose(words): 
    result = " ".join(words) 
    if len(result) > 253: 
     pass # this should not happen! 
    return result 

Il mio problema è che voglio provare a riempire la linea il più possibile. Ad esempio:

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) 

Come posso fare?

Answer 1

non ottimale algoritmo offline veloce 1D bin packing 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 

prestazioni

Testato su /usr/share/dict/words (fornito da words-3.0-20.fc18.noarch) che può fare milioni e mezzo di parole un secondo sul mio lento laptop dual core, con un'efficienza di almeno il 90% con questi parametri:

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

Con limit *= 1.5 ottengo il 92%, con limit *= 2 ottengo il 96% (stesso tempo di esecuzione).

ottimale valore (teorico) si calcola con: math.ceil(len(sep.join(words))/limit)

non efficiente algoritmo di bin-imballaggio può essere garantita a fare meglio

Fonte: http://mathworld.wolfram.com/Bin-PackingProblem.html

Morale della favola

Mentre è interno per trovare la soluzione migliore, penso che per la maggior parte dei casi sarebbe molto meglio usare questo algoritmo per problemi di impacchettamento del bin offline 1D.

Risorse

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

Note

• Non ho usato per il mio textwrap implementazione becau è più lento del mio semplice codice Python. Forse è correlato a: Why are textwrap.wrap() and textwrap.fill() so slow?
• Sembra funzionare perfettamente anche se l'ordinamento non è invertito.

Answer 2

Questo è il bin packing problem; la soluzione è NP-difficile, sebbene esistano algoritmi euristici non ottimali, in primo luogo si adattano prima alla diminuzione e alla riduzione del miglior adattamento. Vedi https://github.com/type/Bin-Packing per le implementazioni.