Как собрать многоуровневый массив?

Написал как можно точно, кручи не смогу, разве что если картинку еще добавлю :D
И так, нужен СУПЕР-ПУПЕР КОД
<?php
// Начало

$a = "Шла саша по шоссе и сосала сушку"; // переменная с текстом

$b = preg_split('-([\W])-u', $a, -1, PREG_SPLIT_NO_EMPTY); // супер-пупер разделитель текста

// ........... СУПЕР-ПУПЕР КОД, который надо найти

print_r($c); // переменная $c после супер-пупер кода

// Конец

Что должно получиться (ЦЕЛЬ)
Array
(
	[0] => Array
		(
			[0] => Шла саша по шоссе и сосала сушку
		)

	[1] => Array
		(
			[0] => Шла
			[1] => саша по шоссе и сосала сушку
		)

	[2] => Array
		(
			[0] => Шла саша
			[1] => по шоссе и сосала сушку
		)

	[3] => Array
		(
			[0] => Шла саша по
			[1] => шоссе и сосала сушку
		)

	[4] => Array
		(
			[0] => Шла саша по шоссе
			[1] => и сосала сушку
		)

	[5] => Array
		(
			[0] => Шла саша по шоссе и
			[1] => сосала сушку
		)

	[6] => Array
		(
			[0] => Шла саша по шоссе и сосала
			[1] => сушку
		)

	[7] => Array
		(
			[0] => Шла
			[1] => саша
			[2] => по шоссе и сосала сушку
		)

	[8] => Array
		(
			[0] => Шла
			[1] => саша по
			[2] => шоссе и сосала сушку
		)

	[9] => Array
		(	[0] => Шла
			[1] => саша по шоссе
			[2] => и сосала сушку
		)

	[10] => Array
		(	[0] => Шла
			[1] => саша по шоссе и
			[2] => сосала сушку
		)

	[11] => Array
		(	[0] => Шла
			[1] => саша по шоссе и сосала
			[2] => сушку
		)

	[12] => Array
		(
			[0] => Шла саша
			[1] => по
			[2] => шоссе и сосала сушку
		)

	[13] => Array
		(
			[0] => Шла саша
			[1] => по шоссе
			[2] => и сосала сушку
		)

	[14] => Array
		(
			[0] => Шла саша
			[1] => по шоссе и
			[2] => сосала сушку
		)

	[15] => Array
		(
			[0] => Шла саша
			[1] => по шоссе и сосала
			[2] => сушку
		)
		
	// И так далее пока не достигнет

	[40] => Array
		(
			[0] => Шла
			[1] => саша
			[2] => по
			[3] => шоссе
			[4] => и
			[5] => сосала
			[6] => сушку
		)
)
  • Вопрос задан
  • 3591 просмотр
Решения вопроса 3
Fesor
@Fesor
Full-stack developer (Symfony, Angular)
Я слегка к вечеру начал туго соображать, но давайте попробуем. Возможно я допущу какое грубое невежество или моя версия алгоритма не слишком интересная... но мне откровенно лень много думать. Так что задачу я решу почти в лоб. Для начала определимся что мы должны сделать...

$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/ggFzJd
array(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 - к сожалению времени не так много... может позже доделаю склейку. Пока так. Суть надеюсь будет ясна. Если кто допилит - буду рад.
Ответ написан
@eandr_67
web-программист (*AMP, Go, JavaScript, вёрстка).
Зачем такие сложности? Всё делается намного проще - без рекурсий и проверок множества дополнительных условий:

$input = 'Шла Саша по шоссе и сосала сушку';

$inp_arr = preg_split('#[[:space:]]+#s', trim($input)); // Список обрабатываемых слов
$current = array(); // Список уже обработанных слов
$result  = array(implode(' ', $inp_arr)); // Добавляем в результат исходную фразу
while (count($inp_arr) > 1) { // Пока в списке обрабатываемых не менее 2 слов
  $head = array(); // Голова списка обрабатываемых слов
  $tail = $inp_arr; // Хвост списка обрабатываемых слов
  while (count($tail) > 1) { // Пока в хвосте не менее 2 слов
    $head[]   = array_shift($tail); // Перенос первого слова хвоста в конец головы
    // Добавляем комбинацию в результат
    $result[] = array_merge($current, array(implode(' ', $head), implode(' ', $tail)));
  }
  $current[] = array_shift($inp_arr); // Перенос первого слова обрабатываемых в уже обработанные
}

var_export($result);


Вариант, который перебирает все комбинации, всё же удобнее сделать рекурсивным, но алгоритмически он проще, т.к. не надо заботиться о том, чтобы в $current было по одному слову:

$input="Шла Саша по шоссе и сосала сушку";
$result=generate(preg_split('#[[:space:]]+#s', trim($input)));
var_export($result);
 
function generate($inp){
  $out=array(implode(' ', $inp));
  $head=array();
  while(count($inp)>1){
    $head[]=array_shift($inp);
    foreach(generate($inp) as $val){
      $out[]=array_merge(array(implode(' ', $head)), (array)$val);
    }
  }
  return $out;
}

Если нужно сортировать по длинам строк, то достаточно изменить порядок обработки: предыдущий вариант начинает перебор с пустой головы и длинного хвоста, а надо с длиной головы и пустого хвоста:

function generate($inp){
  $out=array(implode(' ', $inp));
  $tail=array();
  while(count($inp)>1){
    array_unshift($tail, array_pop($inp));
    foreach(generate($tail) as $val){
      $out[]=array_merge(array(implode(' ', $inp)), (array)$val);
    }
  }
  return $out;
}

Если же нужно отсортировать результат по длинам строк независимо от того, в какой позиции эта строка находится, то проще всего - как и сказал @Fesor - использовать отдельную сортировку результата. Например, вот так:

usort($result, function($val_1, $val_2){
  // Получение кол-ва слов в строках сравниваемых вариантов
  $len_1=array_map(function($data){ return count(preg_split('#[[:space:]]+#s', $data)); }, (array)$val_1);
  $len_2=array_map(function($data){ return count(preg_split('#[[:space:]]+#s', $data)); }, (array)$val_2);

  // Массивы кол-ва слов, отсортированные по убыванию
  $sort_len_1=$len_1;
  $sort_len_2=$len_2;
  rsort($sort_len_1);
  rsort($sort_len_2);

  // Проверяем, что два варианта имеют разное кол-во слов в строках
  for($i=0; $i<count($sort_len_1); $i++){
    if($sort_len_1[$i]!=$sort_len_2[$i]){
      return $sort_len_2[$i]-$sort_len_1[$i];
    }
  }

  // К данному моменту варианты по длинам строк уже отсортированы
  // Этот цикл сортирует варианты с одинаковыми длинами по местоположению длинных строк
  // Если такая сортировка не требуется - удалить цикл
  for($i=0; $i<count($len_1); $i++){
    if($len_1[$i]!=$len_2[$i]){
      return $len_2[$i]-$len_1[$i];
    }
  }

  return 0;
});
Ответ написан
@HaveFun
$text = 'Шла саша по шоссе и сосала сушку';

$arWords = explode(' ',$text);
function implodeAndNest($arWords,$firstElement = null){
  $arResult = array();
  foreach($arWords as $wordNum => $word){
    if($wordNum == 0){
      $result = array(implode(' ',array_slice($arWords,$wordNum)));
    }else{
      $result = array(implode(' ',array_slice($arWords,0,$wordNum)),implode(' ',array_slice($arWords,$wordNum)));
    }
    if(isset($firstElement))
      $result = array_merge(array($firstElement),$result);
    $arResult[] = $result;
  }
  return $arResult;
}

$arResult = array();
foreach($arWords as $wordNum => $word){
  if($wordNum == 0){
    $arResult = implodeAndNest(array_slice($arWords,$wordNum));
  }else{
    $arResult = array_merge($arResult,array_values(implodeAndNest(array_slice($arWords,$wordNum),implode(' ',array_slice($arWords,0,$wordNum)))));
  }
}

// удаляем лишние результаты
$arResult = array_values(array_map("unserialize", array_unique(array_map("serialize", $arResult))));

echo '<pre>';
print_r($arResult);
echo '</pre>';
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы