Berechnen Sie die Schnittmenge von Arrays mit einer Schwelle in PHP

Question

Lassen Sie sich sagen, ich habe folgende Felder:

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

Die Kreuzung die $result = [1] wäre, die einfach genug ist. Aber was wäre, wenn ich die Schnittmenge von denen mit einer minimalen Schwelle von sagen wir 3 wollte? Die Schwellenwerteinrichtung kann ich überspringe ein oder mehr Arrays aus dem Schnittpunkt, solange mein resultierender Schnitt mindestens 3 Elemente aufweist, die in diesem Fall in könnten zur Folge hat:

$result = [1,3,4]; 

1, 3 und 4 sind in $ a, $ b und $ d, aber nicht in $ c, das wegen des Schwellenwerts übersprungen wird. Gibt es eine vorhandene PHP-Klasse, einen Algorithmus oder eine Funktion, mit der ich dies erreichen könnte?

Answer 1

Dazu müssen wir Kombinationen eines Arrays verwenden. Ich habe Kombinationen Algorithmus aus dieser great article verwendet. diesen Algorithmus einstellen können wir die folgende Klasse schreiben:

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

ich versucht habe, selbsterklärende Namen zu Methoden zu geben. Einige Codestücke können mehr optimiert werden (z. B. kann ich die Funktion count mehrmals auf denselben Arrays aufrufen; dies wurde getan, um Variablen-Fiddling zu reduzieren) für die Verwendung in der Produktion.

Also im Grunde ist die Logik ziemlich einfach. Wir generieren alle Kombinationen von Arrays und sortieren sie immer weniger nach der Anzahl der verwendeten Arrays. Dann finden wir die längste Kreuzung für jede Länge von Kombinationen. Eigentlich ist das der schwierigste Teil. Um eine bestimmte Kreuzung zu erhalten, geben wir zuerst eine zurück, die der Schwelle entspricht.

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

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

Hier ist working demo.

Es gibt auch andere Möglichkeiten, alle Kombinationen zu finden, zum Beispiel one from "PHP Cookbook". Sie können wählen, was Ihnen am besten gefällt.

Answer 2

Keine eingebaute Funktion dafür. Sie müssen etwas kurz schreiben wie:

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

Hinweis: Dies erfordert PHP7 für? Operator. Ansonsten verwende etwas wie:

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