查找值的唯一组合，从阵列过滤掉任何重复的对 [英] Find unique combinations of values from arrays filtering out any duplicate pairs

问题描述

使用PHP，我希望找到一组特定长度的独特组合，同时确保没有两个完全相同的值是present在多个组合。举例来说，如果我想找到的3值的所有唯一组合（回退到的2个值的组合，如果3是不可能的），这个数组：

  $阵列=阵列（
    阵列（'1'，'2'），
    阵列（'3'，'4'），
    阵列（'5'，'6'），
）;
 

一组可能的组合是123，456，14，15，16，24，25，26，34，35，36 请注意，每个号码始终合并一次且仅一次具有不同数目。没有重复的数字对出现在任意组合。仅仅是为了清楚起见，尽管123和135将是唯一的组合，只是其中的一个，因为对13发生在这两个将返回。的主要标准是，所有数字都最终分组彼此号，但仅一次。

在最终产品中，数组和值的数量的数量将明显较大的如：

  $阵列=阵列（
    阵列（'1'，'2'，'3'，'4'，'5'，'6'，'7'，'8'），
    阵列（'9'，'10'，'11'，'12'，'13'，'14'，'15'，'16'），
    阵列（'17'，'18'，'19'，'20'，'21'，'22'，'23'，'24'），
    阵列（'25'，'26'，'27'，'28'，'29'，'30'，'31'）
）;
 

任何帮助/ code来完成，这将是最AP preciated。

更新：

我已经采取了强力方法。首先，我使用PEAR包<一href="http://pear.php.net/package/Math_Combinatorics/docs/latest/Combinatorics/_Math_Combinatorics-1.0.0---Combinatorics.php.html"相对=nofollow> Math_Combinatorics 以创建组合，从指定的最大大小的分组和我的工作方式，以对。通过这种方式进行迭代时通过剥离出组内的任何重复的集群，我可以得到所有可能的组合。这code ++工程，但非常占用大量内存。生成的所有组合的32值的6组阵列使用过量的内存1.5G的。有没有更好的算法或方法，将让我用更大的阵列没有用完的内存？这里的code的当前状态：

  require_once'Combinatorics.php;
$组合数学=新Math_Combinatorics;
$阵列=范围（1,20,1）;
$ maxgroup =（6）;
$组合= $ combinatorics-＆GT;组合（$数组，$ maxgroup）;
为（$ C = $ maxgroup-1; $ C＆GT; 1; $ C--）
{
    $梳= $ combinatorics-＆GT;组合（$数组，$ C）;
    $组合= array_merge（$组合，$梳）;
    $梳= NULL;
}
为（$ J = 0; $ J＆LT;的sizeof（$组合）; $ J ++）
{
    为（$ i = sizeof的（$组合）-1; $ I＆GT; = $ J + 1; $我 - ）
   {
        $差异=和array_intersect（$组合[$ J]，$组合[$ i]）;
        如果（计数（$差异）→1）
        {
            取消设置（$组合[$ i]）;
        }
    }
    $组合= array_values​​（$组合）;
}
的print_r（$组合）;
 

解决方案

由于结构只是掩盖其可用的数字，你应该首先展开嵌套的数组。我会在种类和为你做的：

  $数= []
的foreach（$ arrar为$ subarr）{
    的foreach（$ subarr为$ NUM）{
        $编号[] = $ NUM;
    }
}
 

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

接下来，您要执行你的算法寻找独特的组合。对于数组这个小，即使是递归的解决方案会奏效。你不必去尝试所有的组合实现一对多的组合。

Using php, I am looking to find a set of unique combinations of a specified length while making sure that no two identical values are present in more than one combination. For example, if I want to find all unique combinations of 3 values (fallback to combinations of 2 values if 3 are not possible) with this array:

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

One possible set of combinations is 123, 456, 14, 15, 16, 24, 25, 26, 34, 35, 36 Note that each number is always combined once and only once with a different number. No duplicate number pairs show up in any combination. Just for clarity's sake, even though 123 and 135 would be unique combinations, only one of these would be returned since the pair 13 occurs in both. The main criteria is that all numbers are eventually grouped with each other number, but only once.

In the final product, the number of arrays and number of values will be notably larger as in:

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

Any help/code to accomplish this would be most appreciated.

UPDATE:

I've taken the brute force approach. First off, I'm using the pear package Math_Combinatorics to create the combinations, starting with a specified maximum size grouping and working my way down to pairs. This way I can get all possible combinations when iterating through to strip out any duplicate clusters within the groups. This code works but is extremely memory intensive. Generating all combinations for an array of 32 values in groups of 6 uses an excess of 1.5G of memory. Is there a better algorithm or approach that will let me use bigger arrays without running out of memory? Here the current state of the code:

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

解决方案

Since the structure is just obscuring the numbers which are available, you should first unfold the nested arrays. I'll be kind and do that for you:

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

I'm assuming there aren't any duplicate numbers in the input.

Next, you want to perform your algorithm for finding the unique combinations. With array this small, even a recursive solution will work. You don't have to try all the combinatorially-many combinations.

这篇关于查找值的唯一组合，从阵列过滤掉任何重复的对的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！