在PHP中查找数组的子集

我有一个具有属性的关系模式（ABCD）。 我也有一套function依赖关系。

现在我需要确定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的权力集？ 这就是你的问题所暗示的。

一个例子可以在这里find（引用完整性）

 <?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

这里是一个回溯解决scheme。

给定一个返回input集合中所有L长度子集的函数，findL = 2到数据集input长度的所有L长度子集

 <?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));