Existe um algoritmo de tempo linear para dividir o texto uniformemente em linhas de largura máxima. Ele usa SMAWK (ou Knuth & Plass) e significa "uniformemente": http://en.wikipedia.org/wiki/Word_wrap#Minimum_raggedness
Existe um algoritmo ou uma função de custo côncavo para o algoritmo acima, que levaria em conta o número de linhas nas quais eu gostaria que o texto fosse dividido, em vez da largura máxima da linha? Também em tempo linear?
Em outras palavras, estou procurando um algoritmo de quebra de linha (ou formação de parágrafo ou quebra de linha) em que a entrada seja o número desejado de linhas, não a largura desejada.
Apenas para descrever uma abordagem praticamente inutilizável: existem N palavras e espaços N-1 entre cada par de palavras, M é o número de linhas desejado (M <= N). Após cada espaço, pode haver no máximo uma (possivelmente zero) quebra de linha. Agora, o algoritmo tentaria colocar as quebras em cada combinação possível, calculando a "irregularidade" e retornando a melhor. Como fazer isso muito mais rápido?
Além disso, esse problema tem um nome? A que "família" de problemas pertence? (Por exemplo, "embalagem de lixeira") Se eu não precisar da solução perfeitamente ideal, apenas uma muito boa, é possível resolvê-la muito mais rapidamente? (alguma forma de heurística pode ser utilizável, se para uma determinada entrada sempre houver a mesma solução, possivelmente subótima).
Atualizar
Chandra Chekuri sugeriu abaixo "um problema no capítulo sobre programação dinâmica de Kleinberg e Tardos". Foi uma boa leitura, mas lida com a quebra de linha com base na largura e não na contagem de linhas. Pode ser adaptável a esse problema, que é algo que estou tentando descobrir agora. Aqui está um bom link para a solução, eles até afirmam resolvê-la em tempo linear: http://web.media.mit.edu/~dlanman/courses/cs157/HW5.pdf
Além disso, há um capítulo "8.5 O Problema da Partição" no Manual de Projeto de Algoritmo de Skiena que parece exatamente sobre o assunto, eu ainda estou lendo, difícil. (Infelizmente, pelo que entendi, ele tem complexidade quadrática no tempo)
fonte
Respostas:
fonte
Não sei se isso ajuda, mas no final deste comentário alguém implementa o que você deseja em PHP; talvez você possa descobrir o algoritmo.
fonte
wordwrap()
, que por sua vez usa o algoritmo ganancioso (ou seja, não "uniformemente") para encapsular. Mesmo assim, permanece a questão de como "adivinhar" o$width
argumento dewordwrap()
. Mas obrigado pela resposta, de qualquer maneira!