Tách chuỗi dài mà không vi phạm các dòng đầy đủ

Question

Trước khi bạn cho rằng nó trùng lặp (có nhiều câu hỏi hỏi cách chia chuỗi dài mà không vi phạm từ) hãy nhớ rằng vấn đề của tôi hơi khác một chút: thứ tự không quan trọng và tôi đã phù hợp với các từ để sử dụng mọi dòng càng nhiều càng tốt.

Hi,

Tôi đã một tập có thứ tự các từ và tôi muốn kết hợp chúng mà không cần sử dụng nhiều hơn 253 ký tự.

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

Vấn đề của tôi là tôi muốn cố gắng điền vào dòng càng nhiều càng tốt. Ví dụ:

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) 

Tôi làm cách nào?

Answer 1

Non-tối ưu thuật toán ẩn 1D nhanh bin đóng gói 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

Tested trên /usr/share/dict/words (cung cấp bởi words-3.0-20.fc18.noarch) nó có thể làm nửa triệu từ trong một giây trên chậm của tôi máy tính xách tay lõi kép, có hiệu suất ít nhất 90% với các thông số đó:

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

Với limit *= 1.5 Tôi nhận được 92%, với limit *= 2 Tôi nhận được 96% (cùng thời gian thực hiện).

Optimal (lý thuyết) giá trị được tính bằng: math.ceil(len(sep.join(words))/limit)

không có thuật toán bin-đóng gói hiệu quả có thể được đảm bảo để làm tốt hơn

Nguồn: http://mathworld.wolfram.com/Bin-PackingProblem.html

đạo đức của câu chuyện

Trong khi đó là interes ting để tìm giải pháp tốt nhất, tôi nghĩ rằng đối với hầu hết các trường hợp nó sẽ là tốt hơn để sử dụng thuật toán này cho 1D ẩn bin đóng gói vấn đề.

Tài

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

Ghi chú

• Tôi không sử dụng textwrap thi của tôi becau nó chậm hơn mã Python đơn giản của tôi. Có thể liên quan đến: Why are textwrap.wrap() and textwrap.fill() so slow?
• Dường như hoạt động hoàn hảo ngay cả khi sắp xếp không được đảo ngược.

Answer 2

Đây là bin packing problem; giải pháp là NP-hard, mặc dù có tồn tại các thuật toán heuristic không tối ưu, chủ yếu đầu tiên phù hợp với giảm và giảm phù hợp nhất. Xem https://github.com/type/Bin-Packing để triển khai.