पूर्ण भरने वाली लाइनों को तोड़ने के बिना लंबी स्ट्रिंग को विभाजित करना

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

गैर इष्टतम ऑफ़लाइन तेजी -1 डी बिन पैकिंग अजगर एल्गोरिथ्म

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 द्वारा प्रदान की) पर परीक्षण किया गया यह मेरी धीमी गति पर एक दूसरे में पांच लाख शब्द क्या कर सकते हैं दो पैरा कोर लैपटॉप, उन पैरामीटर के साथ कम से कम 90% की दक्षता के साथ:

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

limit *= 1.5 के साथ मुझे limit *= 2 के साथ 92% मिलता है, मुझे 96% (समान निष्पादन समय) मिलता है।

इष्टतम (सैद्धांतिक) मूल्य के साथ की जाती है: math.ceil(len(sep.join(words))/limit)

कोई कुशल बिन-पैकिंग एल्गोरिथ्म बेहतर

स्रोत करने के लिए गारंटी दी जा सकती: http://mathworld.wolfram.com/Bin-PackingProblem.html

कहानी का नैतिक

हालांकि यह पूर्णांक है सबसे अच्छा समाधान खोजने के लिए, मुझे लगता है कि ज्यादातर मामलों के लिए 1 डी ऑफ़लाइन बिन पैकिंग समस्याओं के लिए इस एल्गोरिदम का उपयोग करना बेहतर होगा।

संसाधन

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

नोट्स

• मैं अपने कार्यान्वयन के लिए textwrap का उपयोग नहीं किया becau यह मेरे सरल पायथन कोड से धीमा है। हो सकता है कि इसके साथ संबंधित है: Why are textwrap.wrap() and textwrap.fill() so slow?
• यह पूरी तरह से काम करने के लिए भले ही छंटाई वापस नहीं लिया गया है लगता है।

Answer 2

यह bin packing problem है; समाधान एनपी-हार्ड है, यद्यपि गैर-इष्टतम ह्युरिस्टिक एल्गोरिदम मौजूद हैं, मुख्य रूप से पहले फिट कम हो रहा है और सबसे अच्छा फिट कम हो रहा है। कार्यान्वयन के लिए https://github.com/type/Bin-Packing देखें।