CODEWITHSUNDEEP
phparraysmultidimensional-array
PressingOnAlways
PressingOnAlways

Reputation: 12356

PHP: Enumerate All Possible Combinations in Multi-dimensional Array

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.

Upvotes: 1

Views: 579

Answers (3)

Mikhail Gerasimov
Mikhail Gerasimov

Reputation: 39546

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))

Upvotes: 2

Michael
Michael

Reputation: 6517

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;
}

Upvotes: 1

Roman Hocke
Roman Hocke

Reputation: 4239

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);

Upvotes: 1

Related Questions