가장 균형 잡힌 방식으로 문자열 배열을 분해하기위한 알고리즘 권장 사항

Question

문자열의 배열이 임의의 길이 (예 : 30-45)이며 특정 페이지 수 (예 : 15)에 맞게 다시 배열하려고합니다.).

가능한 한 균등하게 페이지 사이에 문자열을 배포하여 페이지 당 총 문자열 수에 관계없이 모든 페이지가 가능한 한 총 문자 길이에 근접하도록하고 싶습니다. 또한 문자열 순서를 보존해야하므로 배열을 재정렬 할 수 없습니다.

이 문제를 해결하기 위해 권장할만한 알고리즘이 있습니까? 아니면 모호한 접근법을 택할 것입니까? 감사!

Answer 1

한 가지 방법은 텍스트를 http://en.wikipedia.org/wiki/TeX으로 포맷하는 것입니다. 줄 바꿈 알고리즘은 최적이며 동적 프로그래밍을 기반으로합니다. 불행히도 페이지를 깨는 알고리즘은 최적이 아닙니다. 쉽게 찾을 수있을만큼 좋을 것이라고 기대합니다.

고정 된 수의 문자를위한 공간이있는 각 페이지를 모델링 할 수 있다면 실제로 동적 프로그래밍 솔루션이 있습니다. 최적의 위치에 14 페이지 씩 나누는 방법을 찾아야합니다. 왼쪽에서 오른쪽으로 그리고 페이지 나누기를위한 가능한 각 장소에서 작업하면 이전 텍스트에서 k-1 페이지 나누기를 삽입하고 k 번째 페이지 나누기가 가능한 위치에서 끝내는 최상의 방법으로 전체 고르지 않은 패널티를 계산합니다 . k = 1..14에 대해 이렇게하십시오. 새로운 장소에서 총 페널티를 계산할 때 이전에 계산 한 정보를 왼쪽에 사용할 수 있습니다.

텍스트가 끝나면 왼쪽에 14 페이지 나누기를 삽입하는 가장 좋은 방법은 불균형 페널티를 계산하는 데 사용할 수 있습니다. 계산 기록을 왼쪽에 보관 한 경우 14 페이지 나누기 중 가장 오른쪽에있는 부분을 찾아 낼 수도 있습니다. 거기로 돌아가서 13 번째 페이지 나누기가 있어야하는 곳을 찾은 다음 모든 페이지 나누기 위치를 찾을 때까지 계속 작업 할 수 있습니다.

Answer 2

두 단계로 접근합니다. 먼저 대략적인 솔루션을 작성한 다음 해당 솔루션을 개선하십시오.

먼저 문자열 목록을 살펴본 다음 각 문자열을 가장 많은 공간이 남아있는 페이지로 차례로 할당하십시오. 마지막 페이지 문자열을 이전 페이지에 재분배 할 수있는 충분한 공간이 있는지 확인하여 필요한 페이지 수를 줄이는 것이 좋습니다.

두 번째로, 남은 공간이 가장 많고 적은 페이지를 선택하십시오. 두 개의 페이지에 남아있는 공간이 더 가까워 지도록 더 긴 문자열을 다른 문자열로부터 긴 문자열로 바꾸십시오. 모든 페이지에서 적절한 균형을 잡을 때까지 반복하십시오 (무한 루프가되지 않도록하십시오).

이것은 대략적인 해결책이 아닌 정확한 결과이지만, 합리적인 결과를 신속하게 산출 할 수 있어야합니다.

Answer 3

총 문자 수를 전체 페이지 수로 나누고 문장을 추가 할 때 페이지 당 목표 문자 수에 가까워 질 때까지 간단하지 않습니까? 결국 중간에 깨질 수있는 페이지를 스패닝 할 문장이 생깁니다. 해당 문장의 대부분이 현재 페이지에 맞으면 그 페이지를 놓고 다음 페이지를 위해 연기하십시오.

chars_left = 0 
chars_per_page = total_chars/total_pages 
for i = 0 .. total_pages 
    chars_left += chars_per_page 
    while (chars_left > 0) 
     s = get_next_sentence 
     if s.length/2 > chars_left then break 
     page.add(s) 
     chars_left -= s.length 
    endwhile 
endfor 

Answer 4

euclidian rythms 생성 알고리즘을 사용할 수 있습니다. 유클리드 리듬은 여러 비트에 걸쳐 균등하게 퍼져 나가는 리듬입니다.당신이 10 개 위치에 걸쳐 분산 할 네 박자가 있다면 그래서 당신은 얻을 것이다 :

..x.x..x.x 

을 이제 10 개 문자열이 있고 네 개의 페이지를 분산 할 것인지, 그냥 페이지를 추가 X 표시가 각각의 문자열 후 휴식 :

string1 
string2 
string3 

string4 
string5 

string6 
string7 
string8 

string9 
string10 

당신은 또한 모든 페이지 사이에 고르게 퍼져 얻을 페이지 당 문자열과 짧은 페이지의 거의 일정한 수를 달성 그 방법을.

알고리즘은 상당히 간단하며 gcd를 계산하기위한 euclidian 알고리즘을 기반으로하며 몇 줄에 구현할 수 있습니다. 또한 많은 페이지와 요소가있는 경우에도 상당히 빠릅니다.