我有一个带有属性 (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')
代码不应该很大，但由于某种原因我无法理解它。
使用 php array_merge 我们可以有一个不错的简短的 powerSet 函数
// ["A", "B", "C"]
// [[],["A"],["B"],["A","B"],["C"],["A","C"],["B","C"],["A","B","C"]]
function powerSet(array $array) : array {
// add the empty set
$results = [[]];
foreach ($array as $element) {
foreach ($results as $combination) {
$results[] = [...$combination, $element];
}
}
return $results;
}
您想要
$attributes可以在here找到示例（为了完整性而引用）
<?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;
}
这里有一个回溯解决方案。
给定一个返回输入集的所有 L 长度子集的函数，找到从 L = 2 到数据集输入长度的所有 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));
基于@Yada的回答，这将生成数组的幂集，但在每个子集中保留原始数组的键（返回值仍然按数字和顺序索引）。如果您需要关联数组的子集，这非常有用。
子集还保留原始数组的元素顺序。我在
$resultsfunction power_set($array) {
$results = [[]];
foreach ($array as $key => $value) {
foreach ($results as $combination) {
$results[] = $combination + [$key => $value];
}
}
# array_shift($results); # uncomment if you don't want the empty set in your results
$order = array_map('count', $results);
uksort($results, function($key_a, $key_b) use ($order) {
$comp = $order[$key_a] - $order[$key_b]; # change only this to $order[$key_b] - $order[$key_a] for descending size
if ($comp == 0) {
$comp = $key_a - $key_b;
}
return $comp;
});
return array_values($results);
}
鉴于OP的输入，
var_dump(power_set(['A', 'B', 'C', 'D']));array(16) {
[0] =>
array(0) {
}
[1] =>
array(1) {
[0] =>
string(1) "A"
}
[2] =>
array(1) {
[1] =>
string(1) "B"
}
[3] =>
array(1) {
[2] =>
string(1) "C"
}
[4] =>
array(1) {
[3] =>
string(1) "D"
}
[5] =>
array(2) {
[0] =>
string(1) "A"
[1] =>
string(1) "B"
}
[6] =>
array(2) {
[0] =>
string(1) "A"
[2] =>
string(1) "C"
}
[7] =>
array(2) {
[1] =>
string(1) "B"
[2] =>
string(1) "C"
}
[8] =>
array(2) {
[0] =>
string(1) "A"
[3] =>
string(1) "D"
}
[9] =>
array(2) {
[1] =>
string(1) "B"
[3] =>
string(1) "D"
}
[10] =>
array(2) {
[2] =>
string(1) "C"
[3] =>
string(1) "D"
}
[11] =>
array(3) {
[0] =>
string(1) "A"
[1] =>
string(1) "B"
[2] =>
string(1) "C"
}
[12] =>
array(3) {
[0] =>
string(1) "A"
[1] =>
string(1) "B"
[3] =>
string(1) "D"
}
[13] =>
array(3) {
[0] =>
string(1) "A"
[2] =>
string(1) "C"
[3] =>
string(1) "D"
}
[14] =>
array(3) {
[1] =>
string(1) "B"
[2] =>
string(1) "C"
[3] =>
string(1) "D"
}
[15] =>
array(4) {
[0] =>
string(1) "A"
[1] =>
string(1) "B"
[2] =>
string(1) "C"
[3] =>
string(1) "D"
}
}
按照@fbstj回答，我更新了功能：
sprintffunction powerSet(array $in, int $minLength = 0): array
{
$return = [];
if ($minLength === 0) {
$return[] = [];
}
for ($i = 1 << count($in); --$i;) {
$out = [];
foreach ($in as $j => $u) {
if ($i >> $j & 1) {
$out[] = $u;
}
}
if (count($out) >= $minLength) {
$return[] = $out;
}
}
return $return;
}
由于幂集函数会大量增加内存负载（2count($in)迭代），请考虑使用Generator:
function powerSet(array $in, int $minLength = 0): \Generator
{
if ($minLength === 0) {
yield [];
}
for ($i = 1 << count($in); --$i;) {
$out = [];
foreach ($in as $j => $u) {
if ($i >> $j & 1) {
$out[] = $u;
}
}
if (count($out) >= $minLength) {
yield $out;
}
}
}
用途：
foreach (powerSet(range(1, 10)) as $value) {
echo implode(', ', $value) . "\n";
}