栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 面试经验 > 面试问答

从多个值列表中查找所有无冲突的值组合

面试问答 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

从多个值列表中查找所有无冲突的值组合

这是自生成代码和蛮力在简单性和性能方面击败大多数算法的情况之一。在先前的答案中,我已经看到了很多递归,数组操作和计算,而实际上您想要做的是:

foreach ($array[0] as $k0 => $v0){    foreach ($array[1] as $k1 => $v1)    {        if ($k1 == $k0)        { continue;        }        foreach ($array[2] as $k2 => $v2)        { if ($k2 == $k1 || $k2 == $k0) {     continue; } $result[] = $v0.$v1.$v2;        }    }}

当然,除非您知道其中有多少个数组,否则您无法编写此代码

$array
。这就是生成的代码很方便的地方:

$array = array(    array('1', '2'),    array('a', 'b', 'c'),    array('x', 'y'));$result = array();$php = '';foreach ($array as $i => $arr){    $php .= 'foreach ($array[' . $i . '] as $k' . $i . ' => $v' . $i . '){';    if ($i > 0)    {        $sep  = 'if (';        $j    = $i - 1;        do        { $php .= $sep . '$k' . $i . ' == $k' . $j; $sep  = ' || ';        }        while (--$j >= 0);        $php .= ') { continue; } ';    }}$php .= '$result[] = $v' . implode('.$v', array_keys($array)) . ';' . str_repeat('}', count($array));eval($php);print_r($result);

请注意,此例程假定它

$array
是从零开始的数字索引数组,如您的示例所示。它将生成上面引用的代码,并针对任意数量的数组进行了调整。


更新资料

这是另一种算法。它仍然是自生成的,但暴力程度较低。我们仍然有嵌套循环,除了每个循环都在数组的副本上工作外,其中外部循环当前使用的键已从该循环的数组中删除。例如,如果值应为(a,b,c),但外部循环使用索引0和2,则删除“
a”(索引0)和“ c”(索引2),剩下的就是“ b”。这意味着循环仅在可能的组合上起作用,我们不再需要任何

if
条件。

此外,这部分也可以应用于先前的算法,我们按从最小到最大的顺序处理值的数组,以确保在当前数组中存在使用过的索引。缺点是它不会以相同的顺序生成组合。它生成相同的组合,只是顺序不同。代码如下:

$a0 = $array[0];foreach ($a0 as $k0 => $v0){    $a2 = $array[2];    unset($a2[$k0]);    foreach ($a2 as $k2 => $v2)    {        $a1 = $array[1];        unset($a1[$k0], $a1[$k2]);        foreach ($a1 as $k1 => $v1)        { $result[] = "$v0$v1$v2";        }    }}

上面的例程在每个循环的开始处设置值的副本,然后删除外部循环使用的值。您可以通过在开始时 只设置一次
值的副本,在使用时删除键(在每个循环的开头)并在释放键时将它们放回(在每个循环的结尾)来改进此过程。 。该例程如下所示:

list($a0,$a1,$a2) = $array;foreach ($a0 as $k0 => $v0){    unset($a1[$k0], $a2[$k0]);    foreach ($a2 as $k2 => $v2)    {        unset($a1[$k2]);        foreach ($a1 as $k1 => $v1)        { $result[] = "$v0$v1$v2";        }        $a1[$k2] = $array[1][$k2];    }    $a1[$k0] = $array[1][$k0];    $a2[$k0] = $array[2][$k0];}

生成上述源代码的实际代码是:

$keys = array_map('count', $array);arsort($keys);$inner_keys = array();foreach ($keys as $k => $cnt){    $keys[$k] = $inner_keys;    $inner_keys[] = $k;}$result = array();$php = 'list($a' . implode(',$a', array_keys($array)) . ')=$array;';foreach (array_reverse($keys, true) as $i => $inner_keys){    $php .= 'foreach ($a' . $i . ' as $k' . $i . ' => $v' . $i . '){';    if ($inner_keys)    {        $php .= 'unset($a' . implode('[$k' . $i . '],$a', $inner_keys) . '[$k' . $i . ']);';    }}$php .= '$result[] = "$v' . implode('$v', array_keys($array)) . '";';foreach ($keys as $i => $inner_keys){    foreach ($inner_keys as $j)    {        $php .= '$a' . $j . '[$k' . $i . ']=$array[' . $j . '][$k' . $i . "];n";    }    $php .= '}';}eval($php);


转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/385522.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号