Страницы

Поиск по вопросам

четверг, 11 июля 2019 г.

Как составить алгоритм для поиска комбинаций в массивах?

Здравствуйте, помогите пожалуйста придумать алгоритм для поиска всех возможных групп из комбинаций. Исходные данные: Массив комбинаций $combinations => [ a => [11, 38], b => [38, 64, 71], c => [11, 24, 38, 65] d => [128, 38, 57, 40] ... ] каждая комбинация в этом массиве может состоять из 2, 3 или 4 чисел Нужно найти все возможные группы из 4х чисел, в которых будут участвовать от 2-х до 4-х комбинаций из массива комбинаций и определить сколько комбинаций входит в группу и каких. В группе должно быть 4 числа, ни больше, ни меньше. Например можно составить группу в которой будут участвовать 2 комбинации (a и b): $group => [11, 38, 64, 71] В эту группу входит первая и вторая комбинация. Третья комбинация (с) уже содержит в себе первую комбинацию (a), т.е. она тоже состоит из двух комбинаций. Как найти группы, в которых будет от 2х до 4х комбинаций? Я нагородил много вложенных циклов и то, работает криво и ищет только среди комбинаций которые состоят из 2х чисел. Код получился огромный и страшный, что даже боюсь показывать его кому-то. А страшный он из-за того, что не могу придумать оптимальный алгоритм поиска групп.


Ответ

Код: # Входящий массив: $ar = array( 'a' => '11, 38', 'b' => '38, 64, 71', 'c' => '11, 24, 38, 65', 'd' => '128, 38, 57, 40' );
# Искомые числа: $in = array('11', '38', '64', '71');
$result = array();
foreach($ar as $key => $value){ $line = explode(',',$value);
foreach($in as $inn){ if(in_array($inn,$line)){ $result[$key]['count']++; $result[$key][] = $inn; } } } print_r($result); Результат работы кода: Array ( [a] => Array ( [count] => 2 [0] => 11 [1] => 38 )
[b] => Array ( [count] => 3 [0] => 38 [1] => 64 [2] => 71 )
[c] => Array ( [count] => 2 [0] => 11 [1] => 38 )
[d] => Array ( [count] => 1 [0] => 38 )
) Надеюсь, что помог. UPD: $ar = array( 'a' => '11,38', 'b' => '38,64,71', 'c' => '11,24,38,65', 'd' => '128,38,57,40', 'e' => '38,115,64', 'f' => '64,11,57,38' ); $line = array(); foreach($ar as $key => $value){ $line[$key] = explode(',',$value); } $r = 1; foreach($line as $keyRes => $res){ $c = 1; foreach($line as $keyRes2 => $res2){ if($c > $r){ $arMerge[$keyRes][$keyRes2] = array_merge($res,$res2); }; $c++; } $r++; } foreach($arMerge as $intKey1 => $intVal1){ foreach($intVal1 as $intKey2 => $intVal2){ foreach($intVal2 as $intVal){ $resAr[$intKey1][$intKey2][] = (int)$intVal; } } } foreach($resAr as $uniqKey1 => $uniqVal1){ foreach($uniqVal1 as $uniqKey2 => $uniqVal2){ if(count(array_unique($uniqVal2)) == 4){ $result[] = $uniqKey1.'-'.$uniqKey2; } } } print_r($result); Результат выполнения: Array ( [0] => a-b [1] => a-c [2] => a-e [3] => a-f [4] => b-e ) Теперь вроде правильно.

Комментариев нет:

Отправить комментарий