最小匹配逻辑

我有一个非常大的数据集，我试图找到满足所有数据集的最小集合。最后一组必须对自己的一个值，该值在所有的数据集最小匹配逻辑

数据的少量样品看起来像

[0] => Array 
    (
     [0] => 21 
     [1] => 21 
     [2] => 21 
    ) 

[1] => Array 
    (
     [0] => 29 
    ) 

[2] => Array 
    (
     [0] => 27 
    ) 

[3] => Array 
    (
     [0] => 21 
     [1] => 21 
     [2] => 21 
     [3] => 39 
     [4] => 39 
     [5] => 43 
    ) 

[4] => Array 
    (
     [0] => 29 
     [1] => 33 
     [2] => 33 
     [3] => 43 
    )

在这种情况下，我需要逻辑返回21，27和29 返回的值需要是与所有数组匹配的最小数值。由于我是一名PHP程序员，因此我使用PHP编写了这个函数。

来源

2012-05-19 David Fairbanks

所以基本上，你想要的最小的共同元素。 –

这可以优化很多。每个数组应该被缩减为不同的元素。如果任何数组是另一个数组的超集，它可以被删除。但其他人不确定。 –

你可以按照这个算法：

测试

$data=array(
      array(21,29,27,57,22), 
      array(22,21,23,24,25,26), 
      array(31) 
      ); 

$map = array(); // keep a map of values and how many times they occur in other sets 
foreach ($data as $setid => $set) { 
    foreach (array_unique($set) as $v) { 
     $map[$v][$setid] = true; 
    } 
} 

function reverseCount(array $a, array $b) 
{ 
    return count($b) - count($a); 
} 

// sort reversed on intersection count 
uasort($map, 'reverseCount'); 

// after sorting the first number will be the one that occurs the most 
// keep track of which sets have been hit 
$setmap = array(); $n = count($data); 
foreach ($map as $v => $sets) { 
    $hits = 0; 
    foreach ($sets as $setid => $dummy) { 
     if (!isset($setmap[$setid])) { 
      --$n; 
      ++$hits; 
      $setmap[$setid] = true; 
     } else { 
      continue; 
     } 
    } 
    if ($hits) { 
     echo "value $v\n"; 
     if (!$n) { 
      // all sets are hit 
      break; 
     } 
    } 
}

这次测试后更新。它没有被证明总是得到正确的结果，因为这被认为是一种贪婪的近似算法。

但我希望它给出了你可以做什么的想法。让我知道，如果有什么困惑你，或者如果我是错误的:)

来源

2012-05-19 14:37:46

给出从timus2001上面的数据集，我没有看到$ setmap或$ map中输出的答案。我喜欢映射结果的想法，我会尽力解决这个问题。 –

@DavidFairbanks给出22和31，答案是不是'$ map'或'$ setmap'本身的btw ...它是从两者中提取的;再次，这个算法并不总是给出最优化的结果，因为那样你可能需要动态编程 –

好像是这样。我会做进一步的测试。谢谢 –

最小匹配逻辑

回答

相关问题