Возможная группировка слов

Question

Это не домашнее задание: Наткнулся этого сценария во время работы на PHP String Differences and Dynamic Restrictions

Учитывая строку n слов, как распределить их в m групп, не изменяя последовательности слов?

Example 1: 
String: "My name is SparKot" 
Groups: 2 (string is split in to two strings) 

Possible groups will be: 
('My', 'name is SparKot'), 
('My name', 'is SparKot'), 
('My name is', 'SparKot') 

с одной и той же строки

Example 2: 
String: "My name is SparKot" 
Groups: 3 (string will be split in to three strings) 

Possible groups will be: 
('My', 'name', 'is SparKot'), 
('My', 'name is', 'SparKot'), 
('My name', 'is', 'SparKot') 

Мой PHP функция() без направления (это, предполагают, чтобы вернуть Многомерные групп):

function get_possible_groups ($orgWords, $groupCount, &$status) { 

    $words = explode (' ', $orgWords); 
    $wordCount = count($words); 

    if ($wordCount < $groupCount) { 
     $status = -1; 
     return; 
    } else if ($wordCount === $groupCount) { 
     $status = 0; 
     return (array_chunk($words, 1)); 
    } 

    for ($idx =0; $idx < $wordCount; $idx) { 
     for ($jdx =0; $jdx < $groupCount; $jdx++) { 

     } 
    } 
// append all arrays to form multidimension array 
// return groupings[][] array 
} 
$status =0; 

$groupings = get_possible_groups('My name is SparKot', 4, $status); 

var_dump($groupings); 

для выше ПРИМЕР- 2 должна быть возвращена:

$groupings = array (
     array ('My', 'name', 'is SparKot'), 
     array ('My', 'name is', 'SparKot'), 
     array ('My name', 'is', 'SparKot')); 

Любые подсказки для решения этой проблемы будут высоко оценены.

Прогресс:

• случай: когда wordCount = groupCount [решено]

Answer 1

Хорошо, так, что мне потребовалось некоторое время, но я думаю, что мне удалось получить это право. Честно говоря, я очень горжусь, так как обычно мне не нравятся алгоритмы. В любом случае, здесь мы идем:

function getPossibleGroups($string, $groups) { 
    $words = explode(' ', $string); 
    $wordCount = count($words); 

    if ($groups === 1) { 
     return array(array($string)); 
    } elseif ($groups > $wordCount) { 
     return null; 
    } elseif ($groups === $wordCount) { 
     return array($words); 
    } 

    $results = array(); 
    // We get every possible result for the first group 
    for ($i = 1; $i <= $wordCount - $groups + 1; $i++) { 
     $firstGroup = implode(' ', array_slice($words, 0, $i)); 

     // Recursively get all posible results for the other groups 
     $otherGroups = getPossibleGroups(implode(' ', array_slice($words, $i)), $groups - 1); 

     // Merge both things 
     $allGroups = array_map(function($v) use ($firstGroup) { 
      return array_merge(array($firstGroup), $v); 
     }, $otherGroups); 

     // Add that to the results variable 
     $results = array_merge($results, $allGroups); 
    } 

    return $results; 
}