在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 class、算法或函数可以用来完成此操作？

Answer 1

没有内置功能。你需要写一些简短的东西，比如：

$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 for ??操作员。否则使用类似：

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

Answer 2

为此，我们必须使用数组的组合。我使用了这个 great article 中的组合算法。调整这个算法我们可以写成下面的class:

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 函数；这样做是为了减少变量摆弄）以供生产使用。

基本上逻辑很简单。我们生成数组的所有组合，并根据使用的数组数量对它们进行递减排序。然后我们找到每个组合长度的最长交集。实际上，这是最难的部分。为了获得一个特定的交叉点，我们 return 第一个与阈值匹配的交叉点。

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

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

这里是working demo。

还有其他方法可以找到所有组合，例如one from "PHP Cookbook"。你可以选择你最喜欢的。

在PHP中计算具有阈值的数组的交集

Calculate the intersection of arrays with a threshold in PHP

php

arrays

intersection