PHP: Find every combination of an Array

27 Oct 2010

All possible combinations

Someone posed an interesting probelm over at sitepoint the other day.

Given an array of words how can you work out each possible combination?

There are a few methods but here's the PHP code for the cleanest:

$words = array('red', 'blue', 'green');   
$num = count($words); 

//The total number of possible combinations 
$total = pow(2, $num);

//Loop through each possible combination  
for ($i = 0; $i < $total; $i++) {  
    //For each combination check if each bit is set 
    for ($j = 0; $j < $num; $j++) { 
       //Is bit $j set in $i? 
        if (pow(2, $j) & $i) echo $words[$j] . ' ';      
    } 
    echo '<br />'; 
}

Which will print:

red
blue
red blue
green
red green
blue green
red blue green

How does this work?

This is fairly straight forward for anyone who knows how to count in binary.

Firstly it works out how many possible combinations there are by working out two to the power of the number of words:

$num = count($words); 
$total = pow(2, $num);

In the example there are 3 words so 8 possible combinations of words (one being no words at all). There are two possible values for each word: present or not present. On or off. The total is worked out by two to the power of the number of words. 2 ^ 3 = 8

The clever part is the loop

Consider this:

for ($i = 0; $i < 8; $i++) {
    echo $i;
}

which prints:

Really basic stuff, but is it helpful? What if those numbers were converted to binary?

for ($i = 0; $i < 8; $i++) {
    echo str_pad(decbin($i), 3, '0', STR_PAD_LEFT)  . '<br/>';
    
}

the str_pad is just there to put in some leading zeros for nicer formatting.

Which prints:

Now we're getting somewhere! If each bit is mapped to an element in the original $words array then effectivley we are looping through turning each element on and off. Starting from 0 words selected to all three.

Divide the numbers into columns and column one maps to "red" column two to "blue" and column three maps to "green"

So the number 1 1 1 would represent: red blue green. Wheres 010 would represent [ nothing ] blue [ nothing ]

The next stage is to loop through each word and see if the bit is set.

for ($j = 0; $j < count($words); $j++) { 
   if (pow(2, $j) & $i) echo $words[$j] . ' ';      
}

This converts the index of the array to the related binary bit. e.g. 1,2,4,8,16 (which is what each digit in binary represents) then uses bitwise and to check whether it's set in the running count. Simple and fun. A good use of the under-utilised bitwise operators.