求值的所有非冲突组合从值多个列表 [英] Finding all non-conflicting combinations of values from multiple lists of values
问题描述
我有以下的数组，它包含值的数组：
$阵列=阵列（
阵列（'1'，'2'），
阵列（'一个'，'B'，'C'），
阵列（'×'，'y'）的，
）;
可以有任意数量的阵列和阵列可以包含任何数量的值。我现在有一张code，这将产生其中一个值是从每个阵列中的所有组合。例如：
1AX，1AY，1BX，1BY，1CX，1cy，2AX，2AY，2BX，2BY，2CX，2CY
不过我确实想仅在每列，即只有一个值坐镇组合。 1AX没有好的，因为所有三个值1，A和X坐在第一列中，1BY没有好的原因是b和y坐在第二列中。因此，从上面的例子只是这些的组合将是有效的：
1cy，2CX
我原本打算只生成所有组合，然后筛选出那些有冲突，但没有规模，因为这是一个过于简单的例子，在实际应用中也将是那里有可能数以百万计的组合情况（包括相互冲突的）。
任何人都可以帮助更好的方法来解决这个问题？我工作在PHP，但任何code示例，清楚地表明了逻辑将是有益的。
在此先感谢。
更新：
我测试过，对一个更大的数据集工作，得到一些基准测试的解决方案，这些都是迄今为止的结果：
$阵列=阵列（
阵列（'1'，'2'，'3'，'1'，'2'，'3'，'1'，'2'，'3'，'1'，'2'，'3'， '1'，'2'，'3'），
阵列（'一个'，'B'，'C'，'D'，'A'，'B'，'C'，'D'，'A'，'B'，'C'，'D'， '一'，'B'，'C'，'D'，'A'，'B'，'C'，'D'），
阵列（X，Y，Z，X，Y，Z，X，Y，Z），
阵列（'1'，'2'，'3'，'1'，'2'，'3'，'1'，'2'，'3'），
阵列（'一个'，'B'，'C'，'D'，'A'，'B'，'C'，'D'，'A'，'B'，'C'，'D'） ，
阵列（X，Y，Z），
）;
约什 - 戴维斯第2个解决方案：
组合：249480
时间：0.3180251121521秒
内存使用：22.012168884277 MB
峰值内存使用量：22.03059387207 MB
约什 - 戴维斯：
组合：249480
时间：1.1172790527344秒
内存使用：22.004837036133 MB
峰值内存使用量：22.017387390137 MB
汤姆·黑格：
组合：249480
时间：5.7098741531372秒
内存使用：39.145843505859 MB
峰值内存使用量：39.145843505859 MB
这是对那些情况下自我生成的code和蛮力将击败大多数算法的简单性和性能之一。在previous答案，我见过很多递归，数组处理和计算，当实际上你想要做的是：
的foreach（$阵列[0]为$ K0 =＆GT; $ V0）
{
的foreach（$阵列[1]为$ K1 =＆GT; $ V1）
{
如果（$ K1 == $ K0）
{
继续;
}
的foreach（$阵列[2] $ K2 =＆GT; $ 2版）
{
如果（$ K2 = = $ K1 || $ K2 == $ K0）
{
继续;
}
$结果[] = $ V0 $ V1 V2 $。;
}
}
}
当然，你可以不写，除非你知道有多少数组在 $阵列。这就是产生code来得心应手：
$阵列=阵列（
阵列（'1'，'2'），
阵列（'一个'，'B'，'C'），
阵列（'X'，'Y'）
）;
$结果=阵列（）;
$ PHP ='';
的foreach（$数组作为$ I =＆GT; $ ARR）
{
$ PHP ='的foreach（$阵'为$ķ$ I ['$我。]'。'=＆GT; $ V'$我。'）{';
如果（$ I大于0）
{
$九月='如果（';
$ J = $ I - 1;
做
{
$ PHP = $翘楚'$ K'。 $我。 == $ K'。 $ D];
$九月='|| ';
}
而（ - $ J＆GT; = 0）;
。$ PHP ='）{继续; };
}
}
$ PHP。='$结果[] = $ V'。爆（'。$ V'，array_keys（$阵列））。 ; 。 str_repeat（}，计数（$阵列））;
的eval（$ PHP）;
的print_r（$结果）;
请注意，这个程序假定 $阵列是一个从零开始的数字索引数组，因为在你的榜样。这将产生code以上报价，调整后的数组任意数量。
更新
下面是另一种算法。它仍然是自我生成的，但不暴力破解。我们仍然嵌套循环，除了每个环路工程，其中当前使用外循环键已经从这个循环的数组中删除数组的一个副本。例如，如果该值应为（A，B，C），但是该外循环使用的索引0和2，我们删除一个（索引0）和c（索引2）和所有我们已经离开是的b。这意味着环路上可能的组合只是工作，我们并不需要一个如果的条件了。
此外，这部分可以被应用到previous算法，以及，我们的过程值的阵列，以便从最小到最大，这样我们保证，在当前的阵列存在使用索引。不足之处是它不会产生相同的顺序组合。它所产生的相同的组合，只要不是以相同的顺序。在code是这样的：
$ A0 = $阵列[0];
的foreach（$ A0为$ K0 =＆GT; $ V0）
{
$ A2 = $阵列[2];
取消设置（$ A2 [$ K0]）;
的foreach（$ A2为$ K2 =＆GT; $ 2版）
{
$ A1 = $阵列[1];
取消设置（$ A1 [$ K0]，$ A1 [$ K2]）;
的foreach（$ A1为$ K1 =＆GT; $ V1）
{
$结果[] =$ V0 $ V1 V2 $;
}
}
}
上面的常规设置的值的在每个循环的开始的副本，然后除去所使用的外环值。您可以改善这个过程中通过设置值的副本的只有一次的开头，因为它们使用的（在每个循环的开始），删除键，并把他们回来，因为他们被释放（在每个循环结束时）。然后，程序是这样的：
列表（$ A0，$ A1，$ A2）= $阵列;
的foreach（$ A0为$ K0 =＆GT; $ V0）
{
取消设置（$ A1 [$ K0]，$ A2 [$ K0]）;
的foreach（$ A2为$ K2 =＆GT; $ 2版）
{
取消设置（$ A1 [$ K2]）;
的foreach（$ A1为$ K1 =＆GT; $ V1）
{
$结果[] =$ V0 $ V1 V2 $;
}
$ A1 [$ K2] = $阵列[1] [$ K2]
}
$ A1 [$ K0 = $阵列[1] [$ K0]
$ A2 [$ K0 = $阵列[2] [$ K0]
}
实际的code，产生上述的来源是：
$键= array_map（'算'，$阵列）;
arsort（$键）;
$ inner_keys =阵列（）;
的foreach（$键为$ K =＆GT; $ CNT）
{
$键[$ K] = $ inner_keys;
$ inner_keys [] = $ K表;
}
$结果=阵列（）;
$ PHP =名单（$一个爆（'，$ A'，array_keys（$阵列））。'）= $阵列;';
的foreach（array_reverse（$键，真）为$ I =＆GT; $ inner_keys）
{
$ PHP ='的foreach（$一个$ I'作为$ K'$我。。。。'=＆GT; $ V'$ I'）{';
如果（$ inner_keys）
{
。$ PHP ='取消设置（$ A'。爆（'[$ K'$我。']，$ A'，$ inner_keys）'[$ K'$我。']）;';
}
}
。$ PHP ='$结果[] =$ V'爆（'$ V'，array_keys（$阵列））。';;
的foreach（$键为$ I =＆GT; $ inner_keys）
{
的foreach（$ inner_keys为$ j）条
{
$ PHP ='$ A。附加$ J。 '[$ K'。 $我。 '] = $阵列['。附加$ J。 '] [$ K'。 $我。 ]; \ N的;
}
。$ PHP ='};
}
的eval（$ PHP）;
I have the following array which contains arrays of values:
$array = array(
array('1', '2'),
array('a', 'b', 'c'),
array('x', 'y'),
);
There can be any number of arrays and an array can contain any number of values. I currently have a piece of code which will generate all combinations where one value is taken from each array. eg:
1ax, 1ay, 1bx, 1by, 1cx, 1cy, 2ax, 2ay, 2bx, 2by, 2cx, 2cy
However what I actually want is only the combinations where only one value sits in each column, ie. 1ax is no good because all three values 1, a and x sit in the first column, 1by is no good because b and y sit in the second column. So from the above example only these combinations would be valid:
1cy, 2cx
I originally planned to just generate all combinations and then filter out the ones with conflicts, but that doesn't scale as this is an oversimplified example, in the real application there's going to be situations where there are potentially millions of combinations (including conflicting ones).
Can anyone help with a better way to solve this? I'm working in PHP, but any code sample that clearly demonstrates the logic would be helpful.
Thanks in advance.
Update:
I've tested the solutions that work against a bigger dataset, to get some benchmarks, these are the results so far:
$array = array(
array('1', '2', '3', '1', '2', '3', '1', '2', '3', '1', '2', '3', '1', '2', '3'),
array('a', 'b', 'c', 'd', 'a', 'b', 'c', 'd', 'a', 'b', 'c', 'd', 'a', 'b', 'c', 'd', 'a', 'b', 'c', 'd'),
array('x', 'y', 'z', 'x', 'y', 'z', 'x', 'y', 'z'),
array('1', '2', '3', '1', '2', '3', '1', '2', '3'),
array('a', 'b', 'c', 'd', 'a', 'b', 'c', 'd', 'a', 'b', 'c', 'd'),
array('x', 'y', 'z'),
);
Josh Davis 2nd Solution:
Combinations: 249480
Time: 0.3180251121521 secs
Memory Usage: 22.012168884277 mb
Peak Memory Usage: 22.03059387207 mb
Josh Davis:
Combinations: 249480
Time: 1.1172790527344 secs
Memory Usage: 22.004837036133 mb
Peak Memory Usage: 22.017387390137 mb
Tom Haigh:
Combinations: 249480
Time: 5.7098741531372 secs
Memory Usage: 39.145843505859 mb
Peak Memory Usage: 39.145843505859 mb
This is one of those cases where self-generated code and brute force will beat most algorithms on simplicity and performance. In previous answers I've seen lots of recursion, array manipulation and computations, when in actuality what you'd want to do is:
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;
}
}
}
Of course, you cannot write this unless you know how many arrays are in $array. That's where generated code comes handy:
$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);
Note that this routine assumes that $array is a zero-based numerically indexed array, as in your example. It will generate the code quoted above, adjusted for an arbitrary number of arrays.
Update
Here's an alternative algorithm. It's still self-generated, but less bruteforce. We still have nested loops, except that each loop works on a copy of the array where keys that are currently used by outer loops have been removed from this loop's array. For example, if the values should be (a,b,c) but the outer loops are using the indices 0 and 2, we remove "a" (index 0) and "c" (index 2) and all we have left is "b". It means that loops work only on possible combinations and we don't need a if condition anymore.
Furthermore, and this part can be applied to the previous algorithm as well, we process the arrays of values in order from the smallest to the largest so that we guarantee that used indices exist in current array. The downside is it doesn't generate the combinations in the same order. It generates the same combinations, just not in the same order. The code looks like this:
$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";
}
}
}
The above routine sets up a copy of the values at the beginning of every loop, then removes values that are used by outer loops. You can improve this process by setting up a copy of the values only once at the beginning, remove the keys as they are used (at the beginning of each loop) and put them back as they are freed (at the end of each loop). The routine then looks like this:
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];
}
The actual code that generates the source above is:
$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);
这篇关于求值的所有非冲突组合从值多个列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
