linear-partition

Source http://sandbox.onlinephpfunctions.com/code/ac3217c37d8d1ba600d5190dbf7b323cb6cb1f32

```
<?php

/**
 * Example: linear_partition([9,2,6,3,8,5,8,1,7,3,4], 3) => [[9,2,6,3],[8,5,8],[1,7,3,4]]
 * @param array $seq
 * @param int $k
 * @return array
 */
function linear_partition(array $seq, $k)
{
    if ($k <= 0) {
        return array();
    }

    $n = count($seq) - 1;
    if ($k > $n) {
        return array_map(function ($x) {
            return array($x);
        }, $seq);
    }

    list($table, $solution) = linear_partition_table($seq, $k);
    $k = $k - 2;
    $ans = array();

    while ($k >= 0) {
        $ans = array_merge(array(array_slice($seq, $solution[$n - 1][$k] + 1, $n - $solution[$n - 1][$k])), $ans);
        $n = $solution[$n - 1][$k];
        $k = $k - 1;
    }

    return array_merge(array(array_slice($seq, 0, $n + 1)), $ans);
}

function linear_partition_table($seq, $k)
{
    $n = count($seq);

    $table = array_fill(0, $n, array_fill(0, $k, 0));
    $solution = array_fill(0, $n - 1, array_fill(0, $k - 1, 0));

    for ($i = 0; $i < $n; $i++) {
        $table[$i][0] = $seq[$i] + ($i ? $table[$i - 1][0] : 0);
    }

    for ($j = 0; $j < $k; $j++) {
        $table[0][$j] = $seq[0];
    }

    for ($i = 1; $i < $n; $i++) {
        for ($j = 1; $j < $k; $j++) {
            $current_min = null;
            $minx = PHP_INT_MAX;

            for ($x = 0; $x < $i; $x++) {
                $cost = max($table[$x][$j - 1], $table[$i][0] - $table[$x][0]);
                if ($current_min === null || $cost < $current_min) {
                    $current_min = $cost;
                    $minx = $x;
                }
            }

            $table[$i][$j] = $current_min;
            $solution[$i - 1][$j - 1] = $minx;
        }
    }

    return array($table, $solution);
}

$terms = array('Archers','Arrows','Bees', 'Zebras','Zebus');
sort($terms);


$mappedToFirstLetter = array_reduce(
    $terms,
    function ($mappedToFirstLetter, $term) {
        $letter = strtolower(substr($term, 0, 1));
        
        if (!isset($mappedToFirstLetter[$letter])) {
            $mappedToFirstLetter[$letter] = [];
        }
        
        $mappedToFirstLetter[$letter][] = $term;
        
        return $mappedToFirstLetter;
    },
    []
);

// Count words for each letter in order to use
// linear partition algorithm.
$countByLetters = array_values(array_map('count', $mappedToFirstLetter));

$numberOfGroups = 4;

$groups = linear_partition($countByLetters, $numberOfGroups);

// Group words using linear partition algorithm results.
$chunked = array_reduce(
    $groups,
    function ($chunked, $group) use (&$mappedToFirstLetter) {
        // Get portion of words.
        $chunk = array_reduce(range(1, count($group)), function ($chunk) use (&$mappedToFirstLetter) {
            $chunk[key($mappedToFirstLetter)] = array_shift($mappedToFirstLetter);
            return $chunk;
        }, []);
        
        // Generate group name using chunk keys.
        $key = preg_replace_callback(
            '/^([a-z])(?:([a-z]*)([a-z]))?$/',
            function ($matches) {
                $matches = array_pad($matches, 4, '');
                return $matches[1] . ($matches[3] ? '-' : '') . $matches[3];
            },
            implode('', array_keys($chunk))
        );
        $chunked[$key] = $chunk;
        
        return $chunked;
    },
    []
);

var_dump($chunked);
```