PHP CookBook

Recipe 4.25 Finding All Element Combinations of an Array

4.25.1 Problem

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

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

4.25.3 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, the outer foreach loop moves through every element of the list; the inner foreach loops through every previous combination created by earlier elements. This is the tricky bit; you need to know exactly how PHP behaves during a foreach.

The array_merge( ) function combines the element with the earlier combinations. Note, however, the $results array added to the new array with array_push() is the one that's cycled through in the foreach. Normally, adding entries to $results causes an infinite loop, but not in PHP, because PHP operates over a copy of the original list. But, when you pop back up a level to the outer loop, and reexecute the foreach with the next $element, it's reset. So, you can operate directly on $results in place and use it as a stack to hold your combinations. By keeping everything as arrays, you're given far more flexibility when it comes to printing out or further subdividing the combinations at a later time.

To remove the empty set, replace the opening line of:

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

with:

// initialize by adding the first element
$results = array(array(array_pop($array)));

Since a one-element array has only one combination — itself — popping off an element is identical to making the first pass through the loop. The double foreach statements don't know they're really starting their processing with the second element in the array.

To print the results with tabs between elements inside the combination and returns between each combination, use the following:

$array = array('Adam', 'Bret', 'Ceff', 'Dave');

foreach (pc_array_power_set($array) as $combination) {
    print join("\t", $combination) . "\n";
}

Here's how to print only three-element sized combinations:

foreach (pc_array_power_set($set) as $combination) {
    if (3 == count($combination)) {
        print join("\t", $combination) . "\n";
    }
}

Iterating over a large set of elements takes a long time. A set of n elements generates 2ⁿ⁺¹ sets. In other words, as n grows by 1, the number of elements doubles.

4.25.4 See Also

Recipe 4.26 for a function that finds all permutation of an array.