Alex Rivera | Logout

Minimum set cover [PHP]

Asked 2010-06-28T08:10:14.710
13

Minimum Set Cover is a question where you must find the minimum number of sets needed to cover every element.
For example, imagine that we have a set of X=array(1,2,3,4,5,6) and 5 another set S, where 

S[1]=array(1, 4) 
S[2] =array(2, 5) 
S[3] =array(3, 6)
S[4] =array(1, 2, 3) 
S[5] =array(4, 5, 6)

The problem is to find minimum number of sets of S which cover every element of X. So obviously the minimum set cover in our case will be S[4] and S[5] because they cover all the elements.
Does anybody have an idea how to implement this code in PHP. Note, that this is NP-complete so there is no fast algorithm to solve it. Any solution in PHP will be welcomed. And BTW it is not a homework, I need to use this algorithm in my web application in order to generate suggestion list.
Thanks in advance.

Update 1
There are many applications of Set Covering Problem. Some of the interesting ones are:

  1. Construction of Optimal logic circuits
  2. Air-crew Scheduling
  3. Assembly line balancing
  4. Information retrieval
  5. Art Gallery problem
  6. Genome Sequencing
  7. Red-Blue SetCover problem

Update 2
For example, here you can see the working version of the problem I mentioned. Here, even it shows visually the sets. But I need the pure PHP code for that, if somebody has it please be kind to provide us with the working example in PHP. Thanks

Update 3
Finally, I have solved the problem in PHP. My solution based on the algorithm proposed on a very famous book called

php algorithm set
Edit
Report

1 Answer

1

here it is, finding 11 solutions for your given example:

function array_set_cover($n,$t,$all=false){
    $count_n = count($n);
    $count = pow(2,$count_n);

    for($i=1;$i<=$count;$i++){
        $total=array();
        $anzahl=0;
        $k = $i;
        for($j=0;$j<$count_n;$j++){
                        if($k%2){
                $total=array_merge($total,$n[$j]);
                        }
            $anzahl+=($k%2);
            $k=$k>>1;
        }
                $total = array_unique($total);
        if(count(array_diff($t,$total)) < 1){
            $loesung[$i] = $anzahl;
            if(!$all){
                break;
            }
        }
    }

    asort($loesung);

    foreach($loesung as $val=>$anzahl){
        $bit = strrev(decbin($val));
        $total=0;
        $ret_this = array();
        for($j=0;$j<=strlen($bit);$j++){
            if($bit[$j]=='1'){
                $ret_this[] = $j;
            }   
        }
        $ret[]=$ret_this;
    }

    return $ret;
}

// Inputs
$s = array();
$s[] = array(1, 4);
$s[] = array(2, 5);
$s[] = array(3, 6);
$s[] = array(1, 2, 3);
$s[] = array(4, 5, 6);

// Output
$x = array(1, 2, 3, 4, 5, 6);

var_dump(array_set_cover($s,$x)); //returns the first possible solution (fuc*** fast)

var_dump(array_set_cover($s,$x,true)); // returns all possible solution (relatively fast when you think of all the needet calculations)

if you call that function without the third parameter, the first found solution is given back (as an array with the array-keys of $s that were used) - if you set the third parameter to true, ALL solutions are given back (in the same format, order by number of used items, so the first one should be the best). retun value is like this:

array(1) { // one solution
  [0]=>
  array(3) { // three items used
    [0]=>
    int(0) // used key 0  -> array(1, 4)
    [1]=>
    int(1) // used key 1 ...
    [2]=>
answered 2010-06-28T10:21:10.787

Your Answer