How would I generate all possible line arrangements of an (x) word string over (y) lines in PHP?

Question

I am trying to write a function that takes the following 2 parameters:

1. A sentence as a string
2. A number of lines as an integer

So if I was to call formatLines("My name is Gary", 2); ...

The possible outcomes would be:

• array("My name is", "Gary");
• array("My name", "is Gary");
• array("My", "name is Gary");

It would return: array("My name", "is Gary"); because the difference in character counts for each line is as small as possible.

So the part I am ultimately stuck on is creating an array of possible outcomes where the words are in the correct order, split over x lines. Once I have an array of possible outcomes I would be fine working out the best result.

So how would I go about generating all the possible combinations?

Regards

Joe

Answer 1

It seems like doing this by creating all possible ways of splitting the text and then determining the best one would be unnecessarily inefficient. You can count the characters and divide by the number of lines to find approximately the right number of characters per line.

function lineSplitChars($text, $lines) {
    if (str_word_count($text) < $lines) {
        throw new InvalidArgumentException('lines must be fewer than word count', 1);
    }

    $width = strlen($text) / $lines;                        // initial width calculation

    while ($width > 0) {

        $result = explode("\n", wordwrap($text, $width));   // generate result

        // check for correct number of lines. return if correct, adjust width if not
        $n = count($result);
        if ($n == $lines) return $result;
        if ($n > $lines) {
            $width++;
        } else {
            $width--;
        };
    }
}

Answer 2

An answer has been accepted here - but this strikes me as a rather cumbersome method for solving the problem when PHP already provides a wordwrap() function which does most of the heavy lifting:

 function format_lines($str, $lines)
 {
     $guess_length=(integer)(strlen($str)/($lines+1));
     do {
         $out=explode("\n", wordwrap($str, $guess_length));
         $guess_length++;
     } while ($guess_length<strlen($str) && count($out)>$lines);
     return $out;
 }

As it stands, it is rather a brute force method, and for very large inputs, a better solution would use optimum searching (adding/removing a larger initial interval then decreasing this in iterations)