Я слегка к вечеру начал туго соображать, но давайте попробуем. Возможно я допущу какое грубое невежество или моя версия алгоритма не слишком интересная... но мне откровенно лень много думать. Так что задачу я решу почти в лоб. Для начала определимся что мы должны сделать...
$words = explode(' ', 'a b c d'); // сразу представим строку как массив для более удобной работы с оным
$expectedResult = [
// 1st level
[
'a b c d e',
],
// 2-ой уровень
[
'a',
'b c d e'
],
[
'a b',
'c d',
],
[
'a b c',
'd'
],
// 3-ий уровень
[
'a',
'b',
'c d',
],
[
'a',
'b c',
'd'
],
[
'a b',
'c',
'd'
],
// 4-ый уровень
[
'a',
'b',
'c',
'd'
]
];
каждый уровень представляет из себя комбинации предыдущего:
то есть для строки "a b c d" первый элемент третьего уровня:
[
'a',
'b',
'c d'
]
можно составить как конкатенацию первого элементов второго уровня строки 'b c d' с добавлением оторванной части
['a'] + ['b', 'c d']
Следовательно можно упростить алгоритм введя рекурсию постоянно уменьшая сложность. Разделяй и влавствуй как говориться. Поскольку нас теперь заботят только элементы первого и второго уровня алгорим существенно упрощается (можно хоть 666 уровней делать, реализация от этого сложнее не становится. Единственный минус - на большой вложенности можно упереться в лимит по стэку - решается заменой стэка на очередь вызовов но это не здесь и не сейчас).
Единственное о чем нам стоит подумать - о логике склеивания кусков и условия выхода из рекурсии.
Допустим у нас 4 слова в строке. Нам нужно собрать все варианты элементов третьего уровня. Для этого нам надо:
1) ['a'] + ['b', 'c d'] - есть наборы для строк "a" и "b c d"
2) ['a'] + ['b с', 'd'] - есть наборы для строк "a" и "b c d"
3) ['a b'] + ['c', 'd'] - есть наборы для строк "a b" и "c d"
На третьем стэпе мы достигли ситуации, при которой у нас вторая часть строки содержит количество слов равной требуемому уровню (два слова для второго уровня). Собирать комбинации больше неизчего. Сделаем это нашим уловием выхода из цикла.
Давайте теперь попробуем соорудить функцию, которая будет корректно отрабатывать первый и второй уровни
function buildLevel(array $words, $level) {
// с первым уровнем все просто
if ($level === 1) return [implode(' ', $words)];
if ($level === 2) {
// со вторым чуть по сложнее...
$result = [];
$chunk = [];
while(count($words) >= $level) {
// отделяем первое слово из "строки" и зановим его к первому "слагаемому"
array_push($chunk, array_shift($words));
$result[] = array_merge([implode(' ', $chunk)], [implode(' ', $words)]);
}
return $result;
}
throw new \Exception(sprintf('Not implemented for level %d for now', $level));
}
Проверям работу:
ideone.com/ggFzJdarray(1) {
[0]=>
string(7) "a b c d"
}
array(3) {
[0]=>
array(2) {
[0]=>
string(1) "a"
[1]=>
string(5) "b c d"
}
[1]=>
array(2) {
[0]=>
string(3) "a b"
[1]=>
string(3) "c d"
}
[2]=>
array(2) {
[0]=>
string(5) "a b c"
[1]=>
string(1) "d"
}
}
все ок, только результаты надо склеить.... Но давайте вспомним одно из основных правил программирования! DRY - do not repeat your self. Что мы видим? Одинаковый код! В обработке второго уровня у нас используется код, который мы уже использовали в обработке первого уровня! Причем дважды! Кошмар! Рефакторим...
$result[] = array_merge(buildLevel($chunk, 1), buildLevel($words, 1));
Теперь вспомним наш замысел... Мы хотели огранизовать рекурсию, и она родимая у нас и выходит. Функция вызывает самою себя понижая уровень. Сложность решения уменьшается, все хорошо. По такому же принципу добавляем обработку третьего уровня. Попробуйте сначала сами и самостоятельно попробуйте побороть проблему "склейки" результатов третьего и второго уровня. Зачем просто унифицируйте решения. Для того что бы поставить логическую точку, я все же предоставлю готовое решение, но постарайтесь все же сами сделать сначала:
ideone.com/fwS4u6 - к сожалению времени не так много... может позже доделаю склейку. Пока так. Суть надеюсь будет ясна. Если кто допилит - буду рад.
