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

Question

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

Рейтинг: 3Ответов: 1Опубликовано: 23.12.2014

Здравствуйте, помогите пожалуйста придумать алгоритм для поиска всех возможных групп из комбинаций.

Исходные данные:

Массив комбинаций

$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х чисел. Код получился огромный и страшный, что даже боюсь показывать его кому-то. А страшный он из-за того, что не могу придумать оптимальный алгоритм поиска групп.

php алгоритм комбинаторика

Источник: Stack Overflow на русском

Answer 1

▲ 1Принят

Код:

# Входящий массив:
$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
)

Теперь вроде правильно.

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

Ответы