为了账号安全,请及时绑定邮箱和手机立即绑定

在PHP中查找数组的子集

在PHP中查找数组的子集

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

3 回答

?
慕标5832272

TA贡献1966条经验 获得超4个赞

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


查看完整回答
反对 回复 2019-09-03
?
墨色风雨

TA贡献1853条经验 获得超6个赞

使用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;

}


查看完整回答
反对 回复 2019-09-03
?
一只萌萌小番薯

TA贡献1795条经验 获得超7个赞

这是一个回溯解决方案。


给定一个返回输入集的所有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));


查看完整回答
反对 回复 2019-09-03
  • 3 回答
  • 0 关注
  • 984 浏览

添加回答

举报

0/150
提交
取消
意见反馈 帮助中心 APP下载
官方微信