PHP Cookbook

4.24. Finding All Element Combinations of an Array

Problem

You want to find all combinations of sets containing some or all of the elements in an array, also called the power set .

Solution

Use the pc_array_power_set( ) function shown in Example 4-5.

Example 4-5. pc_array_power_set( )

function pc_array_power_set($array) {
    // initialize by adding the empty set
    $results = array(array( ));

    foreach ($array as $element)
        foreach ($results as $combination)
            array_push($results, array_merge(array($element), $combination));

    return $results;
}

This returns an array of arrays holding every combination of elements, including the empty set. For example:

$set = array('A', 'B', 'C');
$power_set = pc_array_power_set($set);

$power_set contains eight arrays:

array( );
array('A');
array('B');
array('C');
array('A', 'B');
array('A', 'C');
array('B', 'C');
array('A', 'B', 'C');

Discussion

First, you include the empty set, {} , in the results. After all, one potential combination of a set is to take no elements from it.

The rest of this function relies on the nature of combinations and PHP’s implementation of foreach. Each new element added to the array increases the number of combinations. The new combinations are all the old combinations alongside the new element; a two-element array containing A and B generates four possible combinations: {}, {A}, {B}, and {A, B}. Adding C to this set keeps the four previous combinations but also adds four new combinations: {C}, {A, C}, {B, C}, and {A, B, C}.

Therefore, ...