在 PHP 中查找数组的子集

php arrays functional-programming dependencies subset

2022-08-31 00:09:40

我有一个带有属性的关系架构（A B C D）。我也有一组功能依赖关系。

现在我需要确定 R 属性的所有可能子集的闭包。这就是我陷入困境的地方。我需要学习如何在PHP中查找子集（非重复）。

我的数组是按如下方式存储的。

$ATTRIBUTES = ('A', 'B', 'C', 'D').

所以我的子集应该是

$SUBSET = ('A', 'B', 'C', 'D', 'AB', 'AC', AD', 'BC', 'BD', 'CD', 'ABC', 'ABD', 'BCD', 'ABCD')

代码不应该是大的东西，但由于某种原因，我无法理解它。

答案 1

使用php array_merge我们可以有一个很好的短powerSet函数

function powerSet($array) {
    // add the empty set
    $results = [[]];

    foreach ($array as $element) {
        foreach ($results as $combination) {
            $results[] = array_merge(array($element), $combination);
        }
    }

    return $results;
}

答案 2

你希望的功率集？这就是你的问题所暗示的。$attributes

可以在这里找到一个例子（为完整性而引用）

<?php 
/** 
* Returns the power set of a one dimensional array, a 2-D array. 
* [a,b,c] -> [ [a], [b], [c], [a, b], [a, c], [b, c], [a, b, c] ]
*/ 
function powerSet($in,$minLength = 1) { 
   $count = count($in); 
   $members = pow(2,$count); 
   $return = array(); 
   for ($i = 0; $i < $members; $i++) { 
      $b = sprintf("%0".$count."b",$i); 
      $out = array(); 
      for ($j = 0; $j < $count; $j++) { 
         if ($b{$j} == '1') $out[] = $in[$j]; 
      } 
      if (count($out) >= $minLength) { 
         $return[] = $out; 
      } 
   } 
   return $return; 
}