在PHP中查找数组的子集

Question

我有一个带属性的关系模式（ABCD）。我也有一套功能依赖。现在我需要确定R属性的所有可能子集的闭包。这就是我被困的地方。我需要学习如何在PHP中查找子集（非重复）。我的数组存储方式如下。$ATTRIBUTES = ('A', 'B', 'C', 'D').所以我的子集应该是$SUBSET = ('A', 'B', 'C', 'D', 'AB', 'AC', AD', 'BC', 'BD', 'CD', 'ABC', 'ABD', 'BCD', 'ABCD')代码不应该是大的东西，但由于某种原因，我无法理解它。

Answer 1

你想要的功率集$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; 

} 

Answer 2

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

function powerSet($array) {

    // add the empty set

    $results = array(array());

    foreach ($array as $element) {

        foreach ($results as $combination) {

            $results[] = array_merge(array($element), $combination);

        }

    }

    return $results;

}

Answer 3

这是一个回溯解决方案。

给定一个返回输入集的所有L-lenght子集的函数，找到从L = 2到数据集输入长度的所有L-lenght子集

<?php

function subsets($S,$L) {

    $a = $b = 0;

    $subset = [];

    $result = [];

    while ($a < count($S)) {

        $current = $S[$a++];

        $subset[] = $current;

        if (count($subset) == $L) {

            $result[] = json_encode($subset);

            array_pop($subset);

        }

        if ($a == count($S)) {

            $a = ++$b;

            $subset = [];

        }

    }

    return $result;

}

$S = [ 'A', 'B', 'C', 'D'];

$L = 2;

// L = 1 -> no need to do anything

print_r($S);

for ($i = 2; $i <= count($S); $i++)

    print_r(subsets($S,$i));