Рассчитать пересечение массивов с порогом в переполнении стека

Question

Рассчитать пересечение массивов с порогом в переполнении стека

Допустим, у меня есть следующие массивы:

$a = [1,2,3,4,5];
$b = [1,3,4,5,6];
$c = [1,7,8,9,10];
$d = [1,2,3,4];

Пересечение этих будет $result = [1], что достаточно просто. Но что, если бы я хотел пересечение тех с минимальным порогом, скажем, 3? Порог означает, что я могу пропустить один или несколько массивов с пересечения, если у моего получающегося пересечения есть по крайней мере 3 элемента, что в этом случае может привести к:

$result = [1,3,4];

1, 3 и 4 присутствуют в $ a, $ b и $ d, но не в $ c, который пропускается из-за порога. Существует ли существующий класс, алгоритм или функция PHP, с помощью которых я мог бы достичь этого?

1

arrays intersection php

Решение

Другие решения

Нет встроенной функции для этого. Вам нужно написать что-то короткое, как:

$values = [];

foreach ([$a, $b, $c, $d] as $arr)
foreach ($arr as $value)
$values[$value] = ($values[$value] ?? 0) + 1;

// For threshold of 3
$values = array_keys(array_filter($values, function($a) { return $a >= 3; }));

Примечание: это требует PHP7 для ?? оператор. В противном случае используйте что-то вроде:

$values[$value] = empty($values[$value]) ? 1 : $values[$value] + 1;

0

Источник

Accepted Answer

Для этого мы должны использовать комбинации массива. Я использовал алгоритм комбинаций из этого отличная статья. Настраивая этот алгоритм, мы можем написать следующий класс:

class Intersections
{
protected $arrays;
private $arraysSize;

public function __construct($arrays)
{
$this->arrays = $arrays;
$this->arraysSize = count($arrays);
}

public function getByThreshold($threshold)
{
$intersections = $this->getAll();

foreach ($intersections as $intersection) {
if (count($intersection) >= $threshold) {
return $intersection;
}
}

return null;
}

protected $intersections;
public function getAll()
{
if (is_null($this->intersections)) {
$this->generateIntersections();
}

return $this->intersections;
}private function generateIntersections()
{
$this->generateCombinationsMasks();
$this->generateCombinations();

$combinationSize = $this->arraysSize;
$intersectionSize = 0;

foreach ($this->combinations as $combination) {
$intersection = call_user_func_array('array_intersect', $combination);

if ($combinationSize > count($combination)) {
$combinationSize = count($combination);
$intersectionSize = 0;
}

if (count($intersection) > $intersectionSize) {
$this->intersections[$combinationSize] = $intersection;
$intersectionSize = count($intersection);
}
}
}

private $combinationsMasks;
private function generateCombinationsMasks()
{
$combinationsMasks = [];
$totalNumberOfCombinations = pow(2, $this->arraysSize);

for ($i = $totalNumberOfCombinations - 1; $i > 0; $i--) {
$combinationsMasks[] = str_pad(
decbin($i), $this->arraysSize, '0', STR_PAD_LEFT
);
}

usort($combinationsMasks, function ($a, $b) {
return strcmp(strtr($b, ['']), strtr($a, ['']));
});

$this->combinationsMasks = array_slice(
$combinationsMasks, 0, -$this->arraysSize
);
}

private $combinations;
private function generateCombinations()
{
$this->combinations = array_map(function ($combinationMask) {
return $this->generateCombination($combinationMask);
}, $this->combinationsMasks);
}

private function generateCombination($combinationMask)
{
$combination = [];
foreach (str_split($combinationMask) as $key => $indicator) {
if ($indicator) {
$combination[] = $this->arrays[$key];
}
}

return $combination;
}
}

Я попытался дать понятные названия методам. Некоторые куски кода могут быть оптимизированы больше (например, я называю count работать несколько раз на одних и тех же массивах; это было сделано для того, чтобы уменьшить переменные) для производственного использования.

В общем, логика довольно проста. Мы генерируем все комбинации массивов и сортируем их по количеству используемых массивов. Затем мы найдем самое длинное пересечение для каждой длины комбинаций. На самом деле, это самая сложная часть. Чтобы получить одно конкретное пересечение, мы возвращаем первое, соответствующее порогу.

$intersections = new Intersections([$a, $b, $c, $d]);

var_dump($intersections->getAll());
var_dump($intersections->getByThreshold(3));

Вот рабочая демо.

Есть и другие способы найти все комбинации, например, один из «PHP Cookbook». Вы можете выбрать тот, который вам нравится больше всего.

1