Вычислить пересечение массивов с порогом в PHP

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-класс, алгоритм или функция, с которыми я мог бы это сделать?

Answer 1

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

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)); 

Адрес working demo.

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

Answer 2

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

$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;