使用php,我希望找到一组指定长度的唯一组合,同时确保在多个组合中不存在两个相同的值。例如,如果我想用这个数组找到3个值的所有唯一组合(如果3不可能,则回退到2个值的组合):
$array = array(
array('1', '2'),
array('3', '4'),
array('5', '6'),
);
一组可能的组合是123456、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);
由于结构只是模糊了可用的数字,因此应该首先展开嵌套数组。我会为你做的:
$numbers = []
foreach ($arrar as $subarr) {
foreach ($subarr as $num) {
$numbers[] = $num;
}
}
我假设输入中没有任何重复的数字。
接下来,您要执行用于查找唯一组合的算法。对于这么小的数组,即使是递归解决方案也能工作。你不必尝试所有组合中的许多组合。