php - 查找没有共同元素的组合

Question

我有数组(A、B、C、D)。

我用组合公式在6个组合中从以上4个字母中选出2个

n!/r! (n-r)!

数组(A，B)， 数组(A，C)， 数组(A，D)， 阵列(B，C)， 阵列(B，D)， 数组(C，D)

如何找到没有共同字母的 2 或 3 或 n(应该是动态的)组的组合。所以我希望结果低于 2 人组的组合，

数组(A，B)， 数组(C，D)

数组(A，C)， 数组(B, D),

数组(A, D), 数组(B，C)，

这只是一个示例，但我希望该算法适用于大量数组(我有超过 35000 个数组)。我想找到 2 或 3 或 n 组(应该是动态的)，每个组应该有没有共同元素的数组(所有键应该不同，而不应该重复单个元素)。

Answer 1

您没有说明集合的表示方式，所以我为此目的使用数组。

// The base set
$baseSet = array('A', 'B', 'C', 'D');

// Build the subsets
$subSets = array();
for ($i = 0; $i < 3; $i++) {
    for ($j = $i+1; $j< 4; $j++) {
        $subSets[] = array($baseSet[$i], $baseSet[$j]);
    }
}

这样，解决方案就很简单了:

foreach ($subSets as $subSet) {
    $complement = array_diff($baseSet, $subSet);
    printf("{%s, %s} - {$s, %s}\n",
        $baseSet[0], $baseSet[1],
        $complement[0], $complement[1]
    );
}

一般来说，PHP 提供了很多 set related functions for arrays .

如果你只想比较两个子集，使用array_intersect():

$common = array_intersect($subSet1, $subSet2);
if (empty($common)) {
    echo 'The subsets are distinct.';
} else {
    echo 'The subsets have these elements in common: ' . implode(', ', $common);
}