Как разбить строку на заданное количество строк?

Question

Вот мой вопрос:

Дана строка, которая состоит из разделенных пробелами слов, как я могу разделить, что в N строки (примерно) четной длины, только нарушение на пространствах?

Вот что я собрал из исследования:

Я начал исследовать алгоритмы переноса слов, потому что мне кажется, что это в основном проблема переноса текста. Тем не менее, большинство из того, что я нашел до сих пор (и есть много об обертывании слов), предполагает, что ширина линии является известным входом, а количество строк - результатом. Я хочу наоборот.

Я нашел (очень) несколько вопросов, таких как this, которые кажутся вам полезными. Тем не менее, все они сосредоточены на проблеме как одна из оптимизаций - например, как я могу разбить предложение на заданное количество строк, минимизируя рвение строк или потерянное пустое пространство или что-то в этом роде, и делаю это в линейном (или NlogN или любом другом) времени. Эти вопросы, как правило, остаются без ответа, поскольку оптимизационная часть проблемы относительно «жесткая».

Однако меня не волнует оптимизация. Пока строки (в большинстве случаев) примерно равны, я в порядке, если решение не работает в каждом случае с одним краем или не может быть доказано, что это наименьшая временная сложность. Мне просто нужно решение для реального мира, которое может взять строку и несколько строк (больше 2), и вернуть мне массив строк, которые обычно выглядят довольно ровно.

Вот что я придумал: Я думаю, что у меня есть работоспособный метод для случая, когда N = 3. Я начинаю с первого слова на первой строке, последнего слова на последней строке, а затем итеративно помещаю другое слово в первую и последнюю строки, пока моя общая ширина (измеренная длиной самой длинной линии) перестанет становиться короче , Обычно это работает, но сработает, если ваши самые длинные слова находятся в середине линии, и это не кажется очень обобщаемым для более чем трех строк.

var getLongestHeaderLine = function(headerText) { 
    //Utility function definitions 
    var getLongest = function(arrayOfArrays) { 
    return arrayOfArrays.reduce(function(a, b) { 
     return a.length > b.length ? a : b; 
    }); 
    }; 

    var sumOfLengths = function(arrayOfArrays) { 
    return arrayOfArrays.reduce(function(a, b) { 
     return a + b.length + 1; 
    }, 0); 
    }; 

    var getLongestLine = function(lines) { 
    return lines.reduce(function(a, b) { 
     return sumOfLengths(a) > sumOfLengths(b) ? a : b; 
    }); 
    }; 

    var getHeaderLength = function(lines) { 
    return sumOfLengths(getLongestLine(lines)); 
    } 

    //first, deal with the degenerate cases 
    if (!headerText) 
    return headerText; 

    headerText = headerText.trim(); 

    var headerWords = headerText.split(" "); 

    if (headerWords.length === 1) 
    return headerText; 

    if (headerWords.length === 2) 
    return getLongest(headerWords); 

    //If we have more than 2 words in the header, 
    //we need to split them into 3 lines 
    var firstLine = headerWords.splice(0, 1); 
    var lastLine = headerWords.splice(-1, 1); 
    var lines = [firstLine, headerWords, lastLine]; 

    //The header length is the length of the longest 
    //line in the header. We will keep iterating 
    //until the header length stops getting shorter. 
    var headerLength = getHeaderLength(lines); 
    var lastHeaderLength = headerLength; 
    while (true) { 
    //Take the first word from the middle line, 
    //and add it to the first line 
    firstLine.push(headerWords.shift()); 
    headerLength = getHeaderLength(lines); 
    if (headerLength > lastHeaderLength || headerWords.length === 0) { 
     //If we stopped getting shorter, undo 
     headerWords.unshift(firstLine.pop()); 
     break; 
    } 
    //Take the last word from the middle line, 
    //and add it to the last line 
    lastHeaderLength = headerLength; 
    lastLine.unshift(headerWords.pop()); 
    headerLength = getHeaderLength(lines); 
    if (headerLength > lastHeaderLength || headerWords.length === 0) { 
     //If we stopped getting shorter, undo 
     headerWords.push(lastLine.shift()); 
     break; 
    } 
    lastHeaderLength = headerLength; 
    } 

    return getLongestLine(lines).join(" "); 
}; 

debugger; 
var header = "an apple a day keeps the doctor away"; 

var longestHeaderLine = getLongestHeaderLine(header); 
debugger; 

EDIT: Я потащился JavaScript, потому что в конечном счете, я хотел бы решение я могу реализовать на этом языке. Однако это не слишком критично для проблемы, и я бы принял любое решение, которое работает.

EDIT # 2: В то время как производительность не то, что меня больше всего волнует здесь, мне нужно иметь возможность выполнять любое решение, которое я придумываю ~ 100-200 раз, для строк, которые могут быть до ~ 250 длинные символы. Это будет сделано во время загрузки страницы, поэтому его не нужно навсегда. Например, я обнаружил, что пытаясь разгрузить эту проблему в механизм рендеринга, помещая каждую строку в DIV, и игра с размерами не работает, поскольку она (кажется) невероятно дорога для измерения отображаемых элементов.

Answer 1

Попробуйте это. Для любого разумного N он должен сделать это:

function format(srcString, lines) { 
    var target = ""; 
    var arr = srcString.split(" "); 
    var c = 0; 
    var MAX = Math.ceil(srcString.length/lines); 
    for (var i = 0, len = arr.length; i < len; i++) { 
    var cur = arr[i]; 
    if(c + cur.length > MAX) { 
     target += '\n' + cur; 
    c = cur.length; 
    } 
    else { 
     if(target.length > 0) 
     target += " "; 
     target += cur; 
     c += cur.length; 
    }  
    } 
    return target; 
} 

alert(format("this is a very very very very " + 
      "long and convoluted way of creating " + 
      "a very very very long string",7)); 

Answer 2

Возможно, вы захотите попробовать это решение, используя холст. Это потребует оптимизации, и это всего лишь быстрый снимок, но я думаю, что холст может быть хорошей идеей, так как вы можете рассчитать реальную ширину. Вы также можете настроить шрифт на действительно используемый и т. Д. Важно отметить: это не самый эффективный способ делать вещи. Это создаст массу полотна.

DEMO

var t = `However, I don't care that much about optimization. As long as the lines are (in most cases) roughly even, I'm fine if the solution doesn't work in every single edge case, or can't be proven to be the least time complexity. I just need a real world solution that can take a string, and a number of lines (greater than 2), and give me back an array of strings that will usually look pretty even.`; 


function getTextTotalWidth(text) { 
    var canvas = document.createElement("canvas"); 
    var ctx = canvas.getContext("2d"); 
    ctx.font = "12px Arial"; 
    ctx.fillText(text,0,12); 
    return ctx.measureText(text).width; 
} 

function getLineWidth(lines, totalWidth) { 
    return totalWidth/lines ; 
} 

function getAverageLetterSize(text) { 
    var t = text.replace(/\s/g, "").split(""); 
    var sum = t.map(function(d) { 
    return getTextTotalWidth(d); 
    }).reduce(function(a, b) { return a + b; }); 
    return sum/t.length; 
} 

function getLines(text, numberOfLines) { 
    var lineWidth = getLineWidth(numberOfLines, getTextTotalWidth(text)); 
    var letterWidth = getAverageLetterSize(text); 
    var t = text.split(""); 
    return createLines(t, letterWidth, lineWidth); 
} 

function createLines(t, letterWidth, lineWidth) { 
    var i = 0; 
    var res = t.map(function(d) { 
    if (i < lineWidth || d != " ") { 
     i+=letterWidth; 
     return d; 
    } 
    i = 0; 
    return "<br />"; 
    }) 
    return res.join(""); 
} 

var div = document.createElement("div"); 
div.innerHTML = getLines(t, 7); 
document.body.appendChild(div); 

Answer 3

(Адаптированный здесь, How to partition an array of integers in a way that minimizes the maximum of the sum of each partition?)

Если мы рассмотрим длины слов в виде списка чисел, мы можем двоичный поиск раздела.

Наши max length варьируются от 0 до sum (word-length list) + (num words - 1), meaning the spaces. mid = (range/2). Мы проверяем, может ли быть достигнуто mid путем разбиения на N наборов в O(m) времени: перейдите по списку, добавив (word_length + 1) к текущей части, в то время как текущая сумма меньше или равна mid. Когда сумма пройдет mid, запустите новую часть. Если результат включает N или меньше деталей, то можно достичь mid.

Если mid может быть достигнут, попробуйте использовать более низкий диапазон; в противном случае - более высокий диапазон. Сложность времени - O(m log num_chars). (Вы должны будете также рассмотреть вопрос о том, как удалить пробел в части, то есть, где разрыв строки будет идти, особенности в расчет.)

JavaScript код (адаптировано из http://articles.leetcode.com/the-painters-partition-problem-part-ii):

function getK(arr,maxLength) { 
 
    var total = 0, 
 
     k = 1; 
 

 
    for (var i=0; i<arr.length; i++) { 
 
    total += arr[i] + 1; 
 

 
    if (total > maxLength) { 
 
     total = arr[i]; 
 
     k++; 
 
    } 
 
    } 
 

 
    return k; 
 
} 
 
    
 

 
function partition(arr,n) { 
 
    var lo = Math.max(...arr), 
 
     hi = arr.reduce((a,b) => a + b); 
 

 
    while (lo < hi) { 
 
    var mid = lo + ((hi - lo) >> 1); 
 

 
    var k = getK(arr,mid); 
 

 
    if (k <= n){ 
 
     hi = mid; 
 

 
    } else{ 
 
     lo = mid + 1; 
 
    } 
 
    } 
 

 
    return lo; 
 
} 
 

 
var s = "this is a very very very very " 
 
     + "long and convoluted way of creating " 
 
     + "a very very very long string", 
 
    n = 7; 
 

 
var words = s.split(/\s+/), 
 
    maxLength = partition(words.map(x => x.length),7); 
 

 
console.log('max sentence length: ' + maxLength); 
 
console.log(words.length + ' words'); 
 
console.log(n + ' lines') 
 
console.log('') 
 

 
var i = 0; 
 

 
for (var j=0; j<n; j++){ 
 
    var str = ''; 
 
    
 
    while (true){ 
 
    if (!words[i] || str.length + words[i].length > maxLength){ 
 
     break 
 
    } 
 
    str += words[i++] + ' '; 
 
    } 
 
    console.log(str); 
 
}

Answer 4

Извините, что это C#. Я уже создал свой проект, когда вы обновили свой пост с помощью тега Javascript.

Поскольку вы сказали, что все, о чем вы заботитесь, примерно такая же длина линии ... Я придумал это. Извините за упрощенный подход.

private void DoIt() { 

     List<string> listofwords = txtbx_Input.Text.Split(' ').ToList(); 
     int totalcharcount = 0; 
     int neededLineCount = int.Parse(txtbx_LineCount.Text); 

     foreach (string word in listofwords) 
     { 
      totalcharcount = totalcharcount + word.Count(char.IsLetter); 
     } 

     int averagecharcountneededperline = totalcharcount/neededLineCount; 
     List<string> output = new List<string>(); 
     int positionsneeded = 0; 

     while (output.Count < neededLineCount) 
     { 
      string tempstr = string.Empty; 
      while (positionsneeded < listofwords.Count) 
      { 
       tempstr += " " + listofwords[positionsneeded]; 
       if ((positionsneeded != listofwords.Count - 1) && (tempstr.Count(char.IsLetter) + listofwords[positionsneeded + 1].Count(char.IsLetter) > averagecharcountneededperline))//if (this is not the last word) and (we are going to bust the average) 
       { 
        if (output.Count + 1 == neededLineCount)//if we are writting the last line 
        { 
         //who cares about exceeding. 
        } 
        else 
        { 
         //we're going to exceed the allowed average, gotta force this loop to stop 
         positionsneeded++;//dont forget! 
         break; 
        } 
       } 
       positionsneeded++;//increment the needed position by one 
      } 

      output.Add(tempstr);//store the string in our list of string to output 
     } 

     //display the line on the screen 
     foreach (string lineoftext in output) 
     { 
      txtbx_Output.AppendText(lineoftext + Environment.NewLine); 
     } 

    }