从价值观的多个列表中查找值的所有非冲突组合
https://stackoverflow.com/questions/1378098
-
21-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
我有以下的数组，它包含值数组：
$array = array(
array('1', '2'),
array('a', 'b', 'c'),
array('x', 'y'),
);
有可为任何数量的阵列和阵列可以包含任意数目的值。我现在有一段代码，这将产生其中一个值是从每个阵列采取的所有组合。例如：
1ax, 1ay, 1bx, 1by, 1cx, 1cy, 2ax, 2ay, 2bx, 2by, 2cx, 2cy
但是我想实际上是仅在只有一个值位于在每列中，即组合。 1AX没有好的，因为所有三个值1，并且x在第一列坐，因为B和Y坐在第二列1BY是没有好处的。因此，从上面的例子中只有这些组合是有效的：
1cy, 2cx
我原本打算只生成所有组合，然后筛选出与冲突的，但这并不能扩展，因为这是一个过于简单的例子，在实际应用中也将是那里有可能数以百万计的组合的情况下（包括相互矛盾的）。
任何人都可以用更好的办法来解决这个帮助吗？我在PHP工作，但是这清楚地表明了逻辑的任何代码示例将是有益的。
预先感谢。
更新
我测试过的工作对一个更大的数据集，得到一些基准测试的解决方案，这些都是迄今为止的结果：
$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'),
);
<强>约什戴维斯第二解决方案：
Combinations: 249480
Time: 0.3180251121521 secs
Memory Usage: 22.012168884277 mb
Peak Memory Usage: 22.03059387207 mb
<强>乔希戴维斯：
Combinations: 249480
Time: 1.1172790527344 secs
Memory Usage: 22.004837036133 mb
Peak Memory Usage: 22.017387390137 mb
<强>汤姆黑格：
Combinations: 249480
Time: 5.7098741531372 secs
Memory Usage: 39.145843505859 mb
Peak Memory Usage: 39.145843505859 mb
解决方案
这是的那些情况下，自身生成的代码和蛮力将击败简单性和性能最算法之一。在以前的答案我见过很多递归，数组处理和计算，当在现实中你想要做的是：
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，我们删除“一”（索引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);
其他提示
有趣的问题！事实证明，这比我想象的更复杂，但它似乎工作。
基本策略是先顺序排列最小到最大（他们是在什么样的顺序，所以跟踪我可以输出以正确的顺序的答案）。
我保持索引的阵列的形式的答案输入到列表中的此有序阵列。
现在，该列表是排序的，我可以存储第一正确答案作为阵列（0,1,2，...，N）;
然后，我通过与该答案阵列之外的值（所有不属于该时隙太大的那些）交换它递归到一个功能，用于在第一时隙中有尝试所有值（0以上）。自从我知道了按大小排序，我可以在任何价值转移到时候我交换的权利，而不必担心它是到大对于右侧的插槽。
输出每个有效时隙具有一些疯狂间接撤消所有排序。
很抱歉，如果这看起来混乱。我没有花太多的时间清除它。
<?php
# $lists is an array of arrays
function noconfcombos($lists) {
$lengths = array();
foreach($lists as $list) {
$lengths[] = count($list);
}
# find one solution (and make sure there is one)
$answer = array();
$sorted_lengths = $lengths;
asort($sorted_lengths);
$answer_order_lists = array();
$answer_order_lengths = array();
$output_order = array();
$min = 1;
$max_list_length = 0;
foreach($sorted_lengths as $lists_key => $list_max) {
if($list_max < $min) {
# no possible combos
return array();
}
$answer[] = $min - 1; # min-1 is lowest possible value (handing out colums starting with smallest rows)
$output_order[$lists_key] = $min - 1; # min-1 is which slot in $answers corresponds to this list
$answer_order_lists[] = $lists[$lists_key];
$answer_order_lengths[] = $lengths[$lists_key];
++$min;
}
ksort($output_order);
$number_of_lists = count($lists);
$max_list_length = end($sorted_lengths);
if($max_list_length > $number_of_lists) {
for($i = $number_of_lists; $i < $max_list_length; ++$i) {
$answer[] = $i;
}
$stop_at = $number_of_lists;
} else {
$stop_at = $number_of_lists - 1;
}
# now $answer is valid (it has the keys into the arrays in $list for the
# answer), and we can find the others by swapping around the values in
# $answer.
$ret = array();
$ret[] = noconfcombos_convert($answer, $answer_order_lists, $output_order);
noconfcombos_recurse($ret, $max_list_length, $stop_at, $answer_order_lengths, $answer_order_lists, $output_order, $answer, 0);
return $ret;
}
# try swapping in different indexes into position $index, from the positions
# higher, then recurse
function noconfcombos_recurse(&$ret, $max_list_length, $stop_at, &$lengths, &$lists, &$output_order, $answer, $index) {
if($index < $stop_at) {
noconfcombos_recurse($ret, $max_list_length, $stop_at, $lengths, $lists, $output_order, $answer, $index + 1);
}
for($other = $index + 1; $other < $max_list_length; ++$other) {
if($answer[$other] < $lengths[$index]) { # && $answer[$index] < $lengths[$other]) {
$tmp = $answer[$index];
$answer[$index] = $answer[$other];
$answer[$other] = $tmp;
$ret[] = noconfcombos_convert($answer, $lists, $output_order);
if($index < $stop_at) {
noconfcombos_recurse($ret, $max_list_length, $stop_at, $lengths, $lists, $output_order, $answer, $index + 1);
}
}
}
}
function noconfcombos_convert(&$indexes, &$lists, &$order) {
$ret = '';
foreach($order as $i) {
$ret .= $lists[$i][$indexes[$i]];
}
return $ret;
}
function noconfcombos_test() {
$a = array('1', '2', '3', '4');
$b = array('a', 'b', 'c', 'd', 'e');
$c = array('x', 'y', 'z');
$all = array($a, $b, $c);
print_r(noconfcombos($all));
}
noconfcombos_test();
我想这样的作品。它使用递归走过去就像一棵树的结构。对于每一个分支它跟踪哪些列已被使用。这可能是缓慢的，因为它是一种强制方法。
<?php
$array = array(
array('1', '2'),
array('a', 'b', 'c'),
array('x', 'y'),
);
function f($array, & $result, $colsToIgnore = array(), $currentPath = array()) {
$row = array_shift($array);
$length = count($row);
$isMoreRows = !! count($array);
for ($col = 0; $col < $length; $col++) {
//check whether column has already been used
if (in_array($col, $colsToIgnore)) {
continue;
}
$item = $row[$col];
$tmpPath = $currentPath;
$tmpPath[] = $item;
if ($isMoreRows) {
$tmpIgnoreCols = $colsToIgnore;
$tmpIgnoreCols[] = $col;
f($array, $result, $tmpIgnoreCols, $tmpPath);
} else {
$result[] = implode('', $tmpPath);
}
}
}
$result = array();
f($array, $result);
print_r($result);
可能不是最优雅的方式，但不会把戏 （JavaScript的）
var result = [];
for(i=0;i<arr1.length;i++)
{
for(j=0;j<arr2.length;j++)
{
if(j==i)
continue;
else
{
for(k=0;k<arr3.length;k++)
{
if(k==i||k==j)
continue;
else
{
result.push(arr1[i]+arr2[j]+arr3[k]);
}
}
}
}
}
此可以使用递归使其与阵列的任意量的工作进行重构。如果我发现的时候，我给它一个尝试自己。
PS。我不知道PHP的例子是在Delphi编写。的
修改任意＃阵列递归溶液
type
TSingleArray = array of string;
TMasterArray = array of TSingleArray;
var
solutions: array of integer; // Q&D container to hold currently used indexes of SingleArrays
procedure WriteSolution(const masterArray: TMasterArray);
var
I: Integer;
indexes: string;
solution: string;
begin
for I := 0 to High(solutions) do
begin
indexes := indexes + IntToStr(solutions[I]) + ' ';
solution := solution + masterArray[I][solutions[I]];
end;
Writeln('Solution: ' + solution + ' Using indexes: ' + indexes);
end;
procedure FindSolution(const masterArray: TMasterArray; const singleArrayIndex: Integer; var bits: Integer);
var
I: Integer;
begin
for I := 0 to High(masterArray[singleArrayIndex]) do
begin
//***** Use bit manipulation to check if current index is already in use
if bits and (1 shl I) = (1 shl I ) then continue;
solutions[singleArrayIndex] := I;
Inc(bits, 1 shl I);
//***** If it is not the last array in our masterArray, continue by calling RecursArrays recursivly.
if singleArrayIndex <> High(masterArray) then FindSolution(masterArray, Succ(singleArrayIndex), bits)
else WriteSolution(masterArray);
Dec(bits, 1 shl I);
end;
end;
//***************
// Initialization
//***************
var
I, J: Integer;
bits: Integer;
singleArrayString: string;
masterArray: TMasterArray;
begin
I := 10;
SetLength(masterArray, I);
for I := 0 to High(masterArray) do
begin
SetLength(masterArray[I], High(masterArray) + Succ(I));
singleArrayString := EmptyStr;
for J := 0 to High(masterArray[I]) do
begin
masterArray[I][J] := IntToStr(J);
singleArrayString := singleArrayString + masterArray[I][J];
end;
WriteLn(singleArrayString)
end;
ReadLn;
//****** Start solving the problem using recursion
bits := 0;
SetLength(solutions, Succ(High(masterArray)));
FindSolution(masterArray, 0, bits);
end.
从不同的角度看它：为了构成一个结果行，你需要选择对于每一列的值。每个值应该从不同的源行被拾起。问题是知道的“挑N OUT M的”，或更多数学上，一个组合。
这意味着，因此行对应于源极 - 行索引的阵列。
可以通过开始建立索引阵列这样的（伪代码）建立所有可能的采摘
function combinations( $source ) {
if( count( $source ) == 0 ) return $source;
$result=array();
// build one row
foreach( $source as $index=>$value ) {
$newsource = array_splice( $source, $index, 1 );
$reduced_combinations=combinations( $newsource );
foreach( $reduced_combinations as $reduced_combi ) {
$newrow=array_unshift( $reduced_combi, $value );
$result[]=$newrow;
}
}
return $result;
}
function retrieve_indices( $indices, $arrays ) {
$result=array();
foreach( $indices as $column=>$index ) {
$result[]=$arrays[$index][$column];
}
return $result;
}
$source_arrays = array(
array( "1", "2", "3" ),
array( "a", "b", "c" ),
array( "x", "y", "z" )
);
$index_combinations = combinations( range(0,2) );
$result=array();
foreach( $index_combinations as $combination ) {
$result[]=retrieve_indices( $combination, $source_arrays );
}
另一种选择：
$arr = array(
array('1', '2'),
array('a', 'b', 'c'),
array('x', 'y'),
);
//-----
//assuming $arr consists of non empty sub-arrays
function array_combinations($arr){
$max = 1;
for ($i = 0; $i < count($arr); $i ++){
$max *= count($arr[$i]);
}
$matrix = array();
for ($i = 0; $i < $max; $i ++){
$matrix = array();
}
$c_rep = 1;
for ($i = count($arr) - 1; $i >= 0; $i --){
$c_rep *= ($i < count($arr) - 1)//last sub-array
? count($arr[$i + 1])
: 1;
$k = 0;
while ($k < $max){
for ($t = 0; $t < count($arr[$i]); $t ++){
for ($j = 0; $j < $c_rep; $j ++){
$matrix[$i][$k ++] = $arr[$i][$t];
}
}
}
}
return $matrix;
}
//-----
$matrix = array_combinations($arr);
您的问题是类似于的查找矩阵的决定因素。最好的办法IMHO将填充较小的阵列的一些符号，说“0”，所以它们都具有值的相等数目，在你的例子
$array = array(
array('1', '2', '0'),
array('a', 'b', 'c'),
array('x', 'y', '0'),
);
然后通过每个所述第一阵列值，并且对每个增量阵列的索引环1，并且检查下一个阵列和所述下一列（在第一循环将是“1”和索引将是0递增 - 1 ，然后得到$阵列 1 - 'b' 等），如果你达到“0”，打破，如果达到右边界，第一个索引重置为0，然后做同样的递减，你将拥有所有的组合。这可能是目前还不清楚，我检查链接到图像
尝试这样：
function algorithmToCalculateCombinations($n, $elems) {
if ($n > 0) {
$tmp_set = array();
$res = algorithmToCalculateCombinations($n - 1, $elems);
foreach ($res as $ce) {
foreach ($elems as $e) {
array_push($tmp_set, $ce . $e);
}
}
return $tmp_set;
} else {
return array('');
}
}
$Elemen = array(range(0,9),range('a','z'));
$Length = 3;
$combinations = algorithmToCalculateCombinations($Length, $Elemen);
不隶属于 StackOverflow
