找出没有共同元素的组合

Question

我有一个数组(A, B, C, D)

我使用组合公式从以上4个字母中选择6个组合中的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相关的函数。

如果你只想比较两个子集，使用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);
}