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

Answer 2

使用php array_merge我们可以有一个很好的短powerSet函数function powerSet($array) {&nbsp; &nbsp; // add the empty set&nbsp; &nbsp; $results = array(array());&nbsp; &nbsp; foreach ($array as $element) {&nbsp; &nbsp; &nbsp; &nbsp; foreach ($results as $combination) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; $results[] = array_merge(array($element), $combination);&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; return $results;}

Answer 3

这是一个回溯解决方案。给定一个返回输入集的所有L-lenght子集的函数，找到从L = 2到数据集输入长度的所有L-lenght子集<?phpfunction subsets($S,$L) {&nbsp; &nbsp; $a = $b = 0;&nbsp; &nbsp; $subset = [];&nbsp; &nbsp; $result = [];&nbsp; &nbsp; while ($a < count($S)) {&nbsp; &nbsp; &nbsp; &nbsp; $current = $S[$a++];&nbsp; &nbsp; &nbsp; &nbsp; $subset[] = $current;&nbsp; &nbsp; &nbsp; &nbsp; if (count($subset) == $L) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; $result[] = json_encode($subset);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; array_pop($subset);&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; if ($a == count($S)) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; $a = ++$b;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; $subset = [];&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; return $result;}$S = [ 'A', 'B', 'C', 'D'];$L = 2;// L = 1 -> no need to do anythingprint_r($S);for ($i = 2; $i <= count($S); $i++)&nbsp; &nbsp; print_r(subsets($S,$i));