You want to find all combinations of sets containing some or all of the elements in an array, also called the power set .
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');
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
2n+1 sets. In other words, as
n
grows by 1, the number of elements doubles.
Recipe 4.26 for a function that finds all permutation of an array.
Get PHP Cookbook now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.