php - 从过滤掉任何重复对的数组中查找值的唯一组合

Question

我希望使用 php 找到一组指定长度的唯一组合，同时确保在多个组合中不存在两个相同的值。例如，如果我想使用此数组查找 3 个值的所有唯一组合(如果 3 个值不可能，则回退到 2 个值的组合):

$array = array(
    array('1', '2'),
    array('3', '4'),
    array('5', '6'),
);

一组可能的组合是 123、456、14、15、16、24、25、26、34、35、36请注意，每个数字总是与不同的数字组合一次且仅一次。任何组合中都不会出现重复的数字对。为清楚起见，即使 123 和 135 是唯一组合，也只会返回其中一个，因为对 13 出现在两者中。主要标准是所有数字最终都与其他数字组合在一起，但只有一次。

在最终产品中，数组的数量和值的数量将明显增加，如下所示:

$array = array(
    array('1', '2', '3', '4', '5', '6', '7', '8'),
    array('9', '10', '11', '12', '13', '14', '15', '16'),
    array('17', '18', '19', '20', '21', '22', '23', '24'),
    array('25', '26', '27', '28', '29', '30', '31')
);

任何帮助/代码来实现这一点将不胜感激。

更新:

我采用了蛮力方法。首先，我使用 pear 包 Math_Combinatorics 来创建组合，从指定的最大大小分组开始，一直到成对。通过这种方式，我可以在迭代时获得所有可能的组合，以去除组内的任何重复集群。此代码有效，但非常占用内存。为 6 个一组的 32 个值的数组生成所有组合会使用超过 1.5G 的内存。是否有更好的算法或方法可以让我使用更大的数组而不会耗尽内存？这是代码的当前状态:

require_once 'Combinatorics.php';
$combinatorics = new Math_Combinatorics;
$array = range(1,20,1);
$maxgroup = (6);
$combinations  = $combinatorics->combinations($array, $maxgroup);
for($c=$maxgroup-1;$c>1;$c--)
{
    $comb = $combinatorics->combinations($array, $c);
    $combinations = array_merge($combinations, $comb);
    $comb =  null;
}
for($j=0;$j<sizeof($combinations);$j++)
{
    for($i=sizeof($combinations)-1;$i>=$j+1;$i--)
   {
        $diff = array_intersect($combinations[$j], $combinations[$i]);
        if(count($diff)>1)
        {
            unset($combinations[$i]);
        }
    }
    $combinations = array_values($combinations);
}
print_r($combinations);

Answer 1

由于结构只是模糊了可用的数字，您应该首先展开嵌套数组。我会很友好地为你做这件事:

$numbers = []
foreach ($arrar as $subarr) {
    foreach ($subarr as $num) {
        $numbers[] = $num;
    }
}

我假设输入中没有任何重复的数字。

接下来，您要执行算法来查找唯一组合。对于这么小的数组，即使是递归解决方案也可以。您不必尝试所有的组合 - 许多组合。