PHP: Enumerate All Possible Combinations in Multi-dimensional Array

Question

I have an array:

$array = array ( 'tag1' => array ('apple', 'orange','cherries') ,
                  'tag2' => array ('delicious' , 'yummy', 'tasty', 'good')
                  'tag3' => array ('green', 'red', 'orange')
                );

I would like to produce another array with every possible combination regardless of order but including every combination (power set). For example:

$result = array (
             array(),
             array('tag1' => 'apple'),
             array('tag1' => 'orange'),
             array('tag1' => 'cherries'),
             array('tag2' => 'delicious'),
             array('tag2' => 'yummy'),
             array('tag2' => 'tasty'),
             array('tag2' => 'good'),
             array('tag3' => 'green'),
             array('tag3' => 'red'),
             array('tag3' => 'orange'),
             array('tag1' => 'apple', 'tag2' => 'delicious'),
             array('tag1' => 'apple', 'tag2' => 'yummy'),
             array('tag1' => 'apple', 'tag2' => 'tasty'),
             array('tag1' => 'apple', 'tag2' => 'good'),
             array('tag1' => 'apple', 'tag3' => 'green'),
             array('tag1' => 'apple', 'tag3' => 'red'),
             array('tag1' => 'apple', 'tag3' => 'orange'),
             array('tag1' => 'apple', 'tag2' => 'delicious', 'tag3' => 'green'),
             array('tag1' => 'apple', 'tag2' => 'delicious', 'tag3' => 'red'),
             array('tag1' => 'apple', 'tag2' => 'delicious', 'tag3' => 'orange'),
             ..
);

Does anyone know what function can be written to achieve this? I believe it might have to be a recursive function, but I haven't been able to come up with anything that fits all my requirements so far.

Mikhail Gerasimov · Accepted Answer · 2014-04-29 17:05:48Z

2

function power_set($array) {
    $results = [[]];

    foreach($array as $tag => $features) {
        foreach ($results as $combination) {
            foreach ($features as $feature) {
                array_push($results, array_merge([$tag => $feature], $combination));
            }
        }
    }

    return $results;
}

$array = array(
    'tag1' => array ('apple', 'orange','cherries') ,
    'tag2' => array ('delicious' , 'yummy', 'tasty', 'good'),
    'tag3' => array ('green', 'red', 'orange')
);

print_r(power_set($array))

answered Apr 29, 2014 at 17:05

Mikhail Gerasimov

40.1k20 gold badges126 silver badges172 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Roman Hocke · Accepted Answer · 2014-04-29 16:53:58Z

1

As You say, You may use recursion, like this:

$array = array ( 'tag1' => array ('apple', 'orange','cherries') ,
                  'tag2' => array ('delicious' , 'yummy', 'tasty', 'good'),
                  'tag3' => array ('green', 'red', 'orange')
                );

function expand($sofar, $rest, &$result) {

    if (empty($rest))
        return;

    // get tag name and possible values
    reset($rest);
    $tag = key($rest);
    $values = array_shift($rest);

    // loop through tag's values
    foreach ($values as $value) {

        // prepare new result using $sofar with new tag value added
        $subresult = $sofar;
        $subresult[$tag] = $value;
        $result[] = $subresult;

        // continue expansion of next tag
        expand($subresult, $rest, $result);
    }
}

$result = array();
expand(array(), $array, $result);

print_r($result);

answered Apr 29, 2014 at 16:53

Roman Hocke

4,2411 gold badge22 silver badges36 bronze badges

1 Comment

PressingOnAlways Over a year ago

Good try, unfortunately this function does not get me all the values I am looking for. array( tag2 => '') values nor array($tag3 => '') values are in the results.

Michael · Accepted Answer · 2014-04-29 17:04:14Z

1

I wrote a non-recursive function... :)

function powerset($array)
{
    $results = array(array());
    foreach($array as $key => $values)
    {
        $new_results = array();
        foreach($results as $old_dict)
        {
            foreach($values as $val)
            {
                $new_dict = $old_dict;
                $new_dict[$key] = $val;
                $new_results[] = $new_dict;
            }
        }
        $results = array_merge($results, $new_results);
    }
    return $results;
}

answered Apr 29, 2014 at 17:04

Michael

6,5115 gold badges33 silver badges54 bronze badges

Collectives™ on Stack Overflow

PHP: Enumerate All Possible Combinations in Multi-dimensional Array

3 Answers 3

Comments

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related