How to build an array of combinations on keys in PHP

Question

Before to start explaining my problem I know that most probably there're tons of script of example already available to cover my need, but honestly writing I wasn't able to catch exactly what I want.

My need is to compute a vector listing all the possible combinations of such matrix where the single value may be a key of the possibilities.

To better explain what you mean consider this example:

$start = 10;
$matrix = array(
     10 => array(11,12,13),
     11 => array(21,31,41),
     13 => array(99,98,97),
     41 => array(7,8,9)
)

What I need is to develop an algorithm capable to return a matrix of all the possible combinations considering that the values can be permuted only when the key exists. Or better (and again with an example) I would like to obtain an output like this:

$output = array(
      [0] => array(10 , 11 , 21),   //-- 21 is not a key so the 1st element contains only 3 values
      [1] => array(10 , 11 , 31)
      [2] => array(10 , 11 , 41 , 7)
      [4] => array(10 , 11 , 41 , 8)
      [5] => array(10 , 11 , 41 , 9)
      [6] => array(10 , 12)
      [7] => array(10 , 13 , 99)
      [8] => array(10 , 13 , 98)
      [9] => array(10 , 13 , 97)
 );

Has anyone had a similar problem?

This problem is described usually as enumerating all paths from a given source in a directed graph. This question is related: http://stackoverflow.com/questions/58306/graph-algorithm-to-find-all-connections-between-two-arbitrary-vertices — David Eisenstat, Apr 30 '14 at 18:05

score 1 · Accepted Answer · answered May 02 '14 at 12:21

With some attemps, MAYBE i found a possible solution, if can be usefull :

// variables, start and matrix are the same
$end = array();
$i = 0;
$from ="";
$res = compute($matrix, $start, $from, $i, $end);

// recursive function 
function compute( $matrix, $val, &$from, &$i, &$end){
    // temp base path
    $tmp = $from;
    if( isset($matrix[$val]) ){
        $out = array();
        while(list($c,$item)=each($matrix[$val])){
            if( $c == 0)
                $from .= ($from=="")?($val):(",".$val);

            $r  = compute( $matrix, $item, $from, $i, $end);

            $out[$val][]  = $r;

            if(  is_array($r) ){
                // reset of "base path" to temporary + current val
                $from = ($tmp!="")?($tmp.",".$val):$val;
            }
        }

        return $out;

    }else{
        // ADD ending value to "path"
        $from .=",".$val;
        // ADD complete "path" to END array
        $end[$i] = $from;
        // reset "path" to NODE before
        $from = $tmp;
        // new key for END array
        $i++;

        return $val;
    }
}

Then: I add code to fill $end, most difficult for me and i am not sure about it, after main "core" function: print_r($end); return this:

Array
(
    [0] => 10,11,21
    [1] => 10,11,31
    [2] => 10,11,41,7
    [3] => 10,11,41,8
    [4] => 10,11,41,9
    [5] => 10,12
    [6] => 10,13,99
    [7] => 10,13,98
    [8] => 10,13,97
)

code to build $res is the function recursive core, print_r($res); return this :

Array
(
    [10] => Array
        (
            [0] => Array
                (
                    [11] => Array
                        (
                            [0] => 21
                            [1] => 31
                            [2] => Array
                                (
                                    [41] => Array
                                        (
                                            [0] => 7
                                            [1] => 8
                                            [2] => 9
                                        )

                                )

                        )

                )

            [1] => 12
            [2] => Array
                (
                    [13] => Array
                        (
                            [0] => 99
                            [1] => 98
                            [2] => 97
                        )

                )

        )

)

How to build an array of combinations on keys in PHP

1 Answers1