긴 줄을 깨뜨리지 않고 긴 줄 나누기

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 빈 포장 파이썬 알고리즘

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 

성능

(words-3.0-20.fc18.noarch에서 제공) /usr/share/dict/words을 통해 테스트 내 느린에 두 번째 절반 만 단어를 할 수 듀얼 코어 노트북, 그 매개 변수와 함께 적어도 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

도덕적를

interes 가장 좋은 솔루션을 찾으려면 대부분의 경우 1D 오프라인 빈 포장 문제에이 알고리즘을 사용하는 것이 훨씬 더 좋을 것이라고 생각합니다.

자원

• 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입니다. 비 최적의 휴리스틱 알고리즘이 존재하지만 솔루션은 NP 하드이지만, 주로 첫 번째 적합은 감소하고 가장 적합은 감소합니다. 구현은 https://github.com/type/Bin-Packing을 참조하십시오.