PHP Cookbook/Arrays

From WikiContent

(Difference between revisions)
Jump to: navigation, search
m (1 revision(s))
(Initial conversion from Docbook)

Revision as of 13:36, 7 March 2008

PHP Cookbook


Contents

Introduction

Arrays are lists: lists of people, lists of sizes, lists of books. To store a group of related items in a variable, use an array. Like a list on a piece of paper, the elements in array have an order. Usually, each new item comes after the last entry in the array, but just as you can wedge a new entry between a pair of lines already in a paper list, you can do the same with arrays in PHP.

In many languages, there is only one type of array: what is called a numerical array (or just an array). In a numerical array, if you want to find an entry, you need to know its position within the array, known as an index. Positions are identified by numbers: they start at 0 and work upwards one by one.

In some languages, there is also another type of array: an associative array , also known as a hash . In an associative array, indexes aren't integers, but strings. So, in a numerical array of U.S. presidents, "Abraham Lincoln" might have index 16; in the associative-array version, the index might be "Honest." However, while numerical arrays have a strict ordering imposed by their keys, associative arrays frequently make no guarantees about the key ordering. Elements are added in a certain order, but there's no way to determine the order later.

In a few languages, there are both numerical and associative arrays. But, usually the numerical array $presidents and the associative array $presidents are distinct arrays. Each array type has a specific behavior, and you need to operate on them accordingly. PHP has both numerical and associative arrays, but they don't behave independently.

In PHP, numerical arrays are associative arrays, and associative arrays are numerical arrays. So, which kind are they really? Both and neither. The line between them constantly blurs back and forth from one to another. At first, this can be disorienting, especially if you're used to rigid behavior, but soon you'll find this flexibility an asset.

To assign multiple values to an array in one step, use array( ) :

$fruits = array('Apples', 'Bananas', 'Cantaloupes', 'Dates');

Now, the value of $fruits[2] is 'Cantaloupes'.

array( ) is very handy when you have a short list of known values. The same array is also produced by:

$fruits[0] = 'Apples';
$fruits[1] = 'Bananas';
$fruits[2] = 'Cantaloupes';
$fruits[3] = 'Dates';

and:

$fruits[ ] = 'Apples';
$fruits[ ] = 'Bananas';
$fruits[ ] = 'Cantaloupes';
$fruits[ ] = 'Dates';

Assigning a value to an array with an empty subscript is shorthand for adding a new element to the end of the array. So, PHP looks up the length of $fruits and uses that as the position for the value you're assigning. This assumes, of course, that $fruits isn't set to a scalar value, such as 3, and isn't an object. PHP complains if you try to treat a nonarray as an array; however, if this is the first time you're using this variable, PHP automatically converts it to an array and begins indexing at 0.

An identical feature is the function array_push( ) , which pushes a new value on top of the array stack. However, the $foo[ ] notation is the more traditional PHP style; it's also faster. But, sometimes, using array_push( ) more accurately conveys the stack nature of what you're trying to do, especially when combined with array_pop( ) , which removes the last element from an array and returns it.

So far, we've placed integers and strings only inside arrays. However, PHP allows you to assign any data type you want to an array element: booleans, integers, floating-point numbers, strings, objects, resources, NULL, and even other arrays. So, you can pull arrays or objects directly from a database and place them into an array:

while ($row = mysql_fetch_row($r)) {
    $fruits[ ] = $row;
}

while ($obj = mysql_fetch_object($s)) {
    $vegetables[ ] = $obj;
}

The first while statement creates an array of arrays; the second creates an array of objects. See Recipe 4.3 for more on storing multiple elements per key.

To define an array not using integer keys but string keys, you can also use array( ), but specify the key/value pairs with =>:

$fruits = array('red' => 'Apples', 'yellow' => 'Bananas', 
                'beige' => 'Cantaloupes', 'brown' => 'Dates');

Now, the value of $fruits['beige'] is 'Cantaloupes'. This is shorthand for:

$fruits['red'] = 'Apples';
$fruits['yellow'] = 'Bananas';
$fruits['beige'] = 'Cantaloupes';
$fruits['brown'] = 'Dates';

Each array can only hold one unique value for each key. Adding:

$fruits['red'] = 'Strawberry';

overwrites the value of 'Apples'. However, you can always add another key at a later time:

$fruits['orange'] = 'Orange';

The more you program in PHP, the more you find yourself using associative arrays instead of numerical ones. Instead of creating a numeric array with string values, you can create an associative array and place your values as its keys. If you want, you can then store additional information in the element's value. There's no speed penalty for doing this, and PHP preserves the ordering. Plus, looking up or changing a value is easy because you already know the key.

The easiest way to cycle though an array and operate on all or some of the elements inside is to use foreach:

$fruits = array('red' => 'Apples', 'yellow' => 'Bananas', 
                'beige' => 'Cantaloupes', 'brown' => 'Dates');

foreach ($fruits as $color => $fruit) {
    print "$fruit are $color.\n";
}
Apples are red.
            Bananas are yellow.
            Cantaloupes are beige.
            Dates are brown.
         

Each time through the loop, PHP assigns the next key to $color and the key's value to $fruit. When there are no elements left in the array, the loop finishes.

To break an array apart into individual variables, use list( ) :

$fruits = array('Apples', 'Bananas', 'Cantaloupes', 'Dates');

list($red, $yellow, $beige, $brown) = $fruits;

Specifying an Array Not Beginning at Element 0

Problem

You want to assign multiple elements to an array in one step, but you don't want the first index to be 0.

Solution

Instruct array( ) to use a different index using the => syntax:

$presidents = array(1 => 'Washington', 'Adams', 'Jefferson', 'Madison');

Discussion

Arrays in PHP, like most, but not all, computer languages begin with the first entry located at index 0. Sometimes, however, the data you're storing makes more sense if the list begins at 1. (And we're not just talking to recovering Pascal programmers here.)

In the Solution, George Washington is the first president, not the zeroth, so if you wish to print a list of the presidents, it's simpler to do this:

foreach ($presidents as $number => $president) {
    print "$number: $president\n";
}

than this:

foreach ($presidents as $number => $president) {
    $number++;
    print "$number: $president\n";
}

The feature isn't restricted to the number 1; any integer works:

$reconstruction_presidents = array(16 => 'Lincoln', 'Johnson', 'Grant');

Also, you can use => multiple times in one call:[1]

$whig_presidents = array(9 => 'Harrison', 'Tyler', 12 => 'Taylor', 'Fillmore');

PHP even allows you to use negative numbers in the array( ) call. (In fact, this method works for noninteger keys, too.) What you'll get is technically an associative array, although as we said, the line between numeric arrays and associative arrays is often blurred in PHP; this is just another one of these cases.

$us_leaders = array(-1 => 'George II', 'George III', 'Washington');

If Washington is the first U.S. leader, George III is the zeroth, and his grandfather George II is the negative-first.

Of course, you can mix and match numeric and string keys in one array( ) definition, but it's confusing and very rarely needed:

$presidents = array(1 => 'Washington', 'Adams', 'Honest' => 'Lincoln', 'Jefferson');

This is equivalent to:

$presidents[1]        = 'Washington';   // Key is 1
$presidents[ ]         = 'Adams';        // Key is 1 + 1 => 2
$presidents['Honest'] = 'Lincoln';      // Key is 'Honest'
$presidents[ ]         = 'Jefferson';    // Key is 2 + 1 => 3

See Also

Documentation on array( ) at http://www.php.net/array.

Storing Multiple Elements per Key in an Array

Problem

You want to associate multiple elements with a single key.

Solution

Store the multiple elements in an array:

$fruits = array('red' => array('strawberry','apple'),
                'yellow' => array('banana'));

Or, use an object:

while ($obj = mysql_fetch_object($r)) {
    $fruits[ ] = $obj;
}

Discussion

In PHP, keys are unique per array, so you can't associate more than one entry in a key without overwriting the old value. Instead, store your values in an anonymous array:

$fruits['red'][ ] = 'strawberry';
$fruits['red'][ ] = 'apple';
$fruits['yellow'][ ] = 'banana';

Or, if you're processing items in a loop:

while (list($color,$fruit) = mysql_fetch_array($r)) {
    $fruits[$color][ ] = $fruit;
}

To print the entries, loop through the array:

foreach ($fruits as $color=>$color_fruit) {
    // $color_fruit is an array
    foreach ($color_fruit as $fruit) {
        print "$fruit is colored $color.<br>";
    }
}

Or use the pc_array_to_comma_string( ) function from Recipe 4.10.

foreach ($fruits as $color=>$color_fruit) {
    print "$color colored fruits include " . 
        pc_array_to_comma_string($color_fruit) . "<br>";
}

See Also

Recipe 4.10 for how to print arrays with commas.

Initializing an Array to a Range of Integers

Problem

You want to assign a series of consecutive integers to an array.

Solution

Use range($start, $stop) :

$cards = range(1, 52);

Discussion

For increments other than 1, you can use:

function pc_array_range($start, $stop, $step) {
    $array = array();
    for ($i = $start; $i <= $stop; $i += $step) {
        $array[] = $i;
    }
    return $array;
}

So, for odd numbers:

$odd = pc_array_range(1, 52, 2);

And, for even numbers:

$even = pc_array_range(2, 52, 2);

See Also

Recipe 2.5 for how to operate on a series of integers; documentation on range( ) at http://www.php.net/range.

Iterating Through an Array

Problem

You want to cycle though an array and operate on all or some of the elements inside.

Solution

Use foreach :

foreach ($array as $value) {
    // Act on $value
}

Or, to get an array's keys and values:

foreach ($array as $key => $value) {
    // Act II
}

Another technique is to use for :

for ($key = 0, $size = count($array); $key < $size; $key++) {
   // Act III
}

Finally, you can use each( ) in combination with list( ) and while:

reset($array) // reset internal pointer to beginning of array
while (list($key, $value) = each ($array)) {
    // Final Act
}

Discussion

A foreach loop is the shortest way to iterate through an array:

// foreach with values
foreach ($items as $cost) {
    ...
}

// foreach with keys and values
foreach($items as $item => $cost) {
    ...
}

With foreach, PHP iterates over a copy of the array instead of the actual array. In contrast, when using each( ) and for, PHP iterates over the original array. So, if you modify the array inside the loop, you may (or may not) get the behavior you expect.

If you want to modify the array, reference it directly:

reset($items);
while (list($item, $cost) = each($items)) {
    if (! in_stock($item)) { 
        unset($items[$item]);           // address the array directly
    }
}

The variables returned by each( ) aren't aliases for the original values in the array: they're copies, so, if you modify them, it's not reflected in the array. That's why you need to modify $items[$item] instead of $item.

When using each( ), PHP keeps track of where you are inside the loop. After completing a first pass through, to begin again at the start, call reset( ) to move the pointer back to the front of the array. Otherwise, each( ) returns false.

The for loop works only for arrays with consecutive integer keys. Unless you're modifying the size of your array, it's inefficient to recompute the count( ) of $items each time through the loop, so we always use a $size variable to hold the array's size:

for ($item = 0, $size = count($items); $item < $size; $item++) {
    ...
}

If you prefer to count efficiently with one variable, count backwards:

for ($item = count($items) - 1; $item >= 0; $item--) {
    ...
}

The associative version of the for loop is:

for (reset($array); $key = key($array); next($array) ) {
    ...
}

This fails if any element holds a string that evaluates to false, so a perfectly normal value such as 0 causes the loop to end early.

Finally, use array_map( ) to hand off each element to a function for processing:

// lowercase all words
$lc = array_map('strtolower', $words);

The first argument to array_map( ) is a function to modify an individual element, and the second is the array to be iterated through.

Generally, we find these functions less flexible than the previous methods, but they are well-suited for the processing and merging of multiple arrays.

If you're unsure if the data you'll be processing is a scalar or an array, you need to protect against calling foreach with a non-array. One method is to use is_array( ) :

if (is_array($items)) {
    // foreach loop code for array
} else {
    // code for scalar
}

Another method is to coerce all variables into array form using settype( ) :

settype($items, 'array');
// loop code for arrays

This turns a scalar value into a one element array and cleans up your code at the expense of a little overhead.

See Also

Documentation on for at http://www.php.net/for, foreach at http://www.php.net/foreach, while at http://www.php.net/while, each( ) at http://www.php.net/each, reset( ) at http://www.php.net/reset, and array_map( ) at http://www.php.net/array-map.

Deleting Elements from an Array

Problem

You want to remove one or more elements from an array.

Solution

To delete one element, use unset( ):

unset($array[3]);
unset($array['foo']);

To delete multiple noncontiguous elements, also use unset( ):

unset($array[3], $array[5]);
unset($array['foo'], $array['bar']);

To delete multiple contiguous elements, use array_splice( ):

array_splice($array, $offset, $length);

Discussion

Using these functions removes all references to these elements from PHP. If you want to keep a key in the array, but with an empty value, assign the empty string to the element:

$array[3] = $array['foo'] = '';

Besides syntax, there's a logical difference between using unset( ) and assigning '' to the element. The first says "This doesn't exist anymore," while the second says "This still exists, but its value is the empty string."

If you're dealing with numbers, assigning 0 may be a better alternative. So, if a company stopped production of the model XL1000 sprocket, it would update its inventory with:

unset($products['XL1000']);

However, if it temporarily ran out of XL1000 sprockets, but was planning to receive a new shipment from the plant later this week, this is better:

$products['XL1000'] = 0;

If you unset( ) an element, PHP adjusts the array so that looping still works correctly. It doesn't compact the array to fill in the missing holes. This is what we mean when we say that all arrays are associative, even when they appear to be numeric. Here's an example:

// create a "numeric" array
$animals = array('ant', 'bee', 'cat', 'dog', 'elk', 'fox');
print $animals[1];  // prints 'bee'
print $animals[2];  // prints 'cat'
count($animals);    // returns 6

// unset( )
unset($animals[1]); // removes element $animals[1] = 'bee'
print $animals[1];  // prints '' and throws an E_NOTICE error
print $animals[2];  // still prints 'cat'
count($animals);    // returns 5, even though $array[5] is 'fox'

// add new element
$animals[ ] = 'gnu'; // add new element (not Unix)
print $animals[1];  // prints '', still empty
print $animals[6];  // prints 'gnu', this is where 'gnu' ended up
count($animals);    // returns 6 

// assign ''
$animals[2] = '';   // zero out value
print $animals[2];  // prints ''
count($animals);    // returns 6, count does not decrease

To compact the array into a densely filled numeric array, use array_values( ) :

$animals = array_values($animals);

Alternatively, array_splice( ) automatically reindexes arrays to avoid leaving holes:

// create a "numeric" array
$animals = array('ant', 'bee', 'cat', 'dog', 'elk', 'fox');
array_splice($animals, 2, 2);
print_r($animals);
Array
               (
                   [0] => ant
                   [1] => bee
                   [2] => elk
                   [3] => fox
               )
            

This is useful if you're using the array as a queue and want to remove items from the queue while still allowing random access. To safely remove the first or last element from an array, use array_shift( ) and array_pop( ), respectively.

However, if you find yourself often running into problems because of holes in arrays, you may not be "thinking PHP." Look at the ways to iterate through the array in Recipe 4.5 that don't involve using a for loop.

See Also

Recipe 4.5 for iteration techniques; documentation on unset( ) at http://www.php.net/unset, array_splice( ) at http://www.php.net/array-splice, and array_values( ) at http://www.php.net/array-values.

Changing Array Size

Problem

You want to modify the size of an array, either by making it larger or smaller than its current size.

Solution

Use array_pad( ) to make an array grow:

// start at three
$array = array('apple', 'banana', 'coconut');

// grow to five
$array = array_pad($array, 5, '');

Now, count($array) is 5, and the last two elements contain the empty string.

To reduce an array, you can use array_splice( ):

// no assignment to $array
array_splice($array, 2);

This removes all but the first two elements from $array.

Discussion

Arrays aren't a predeclared size in PHP, so you can resize them on the fly.

To pad an array, use array_pad( ). The first argument is the array to be padded. The next argument is the size and direction you want to pad. To pad to the right, use a positive integer; to pad to the left, use a negative one. The third argument is the value to be assigned to the newly created entries. The function returns a modified array and doesn't alter the original.

Here are some examples:

// make a four-element array with 'dates' to the right
$array = array('apple', 'banana', 'coconut');
$array = array_pad($array, 4, 'dates');
print_r($array);
Array
               (
                   [0] => apple
                   [1] => banana
                   [2] => coconut
                   [3] => dates
               )

// make a six-element array with 'zucchinis' to the left
$array = array_pad($array, -6, 'zucchini');
print_r($array);
Array
               (
                   [0] => zucchini
                   [1] => zucchini
                   [2] => apple
                   [3] => banana
                   [4] => coconut
                   [5] => dates
               )
            

Be careful. array_pad($array, 4, 'dates') makes sure an $array is at least four elements long, it doesn't add four new elements. In this case, if $array was already four elements or larger, array_pad( ) would return an unaltered $array.

Also, if you declare a value for a fourth element, $array[4]:

$array = array('apple', 'banana', 'coconut');
$array[4] = 'dates';

you end up with a four-element array with indexes 0, 1, 2, and 4:

Array
(
    [0] => apple
    [1] => banana
    [2] => coconut
    [4] => dates
)

PHP essentially turns this into an associative array that happens to have integer keys.

The array_splice( ) function, unlike array_pad( ), has the side-effect of modifying the original array. It returns the spliced out array. That's why you don't assign the return value to $array. However, like array_pad( ), you can splice from either the right or left. So, calling array_splice( ) with a value of -2 chops off the last two elements from the end:

// make a four-element array
$array = array('apple', 'banana', 'coconut', 'dates');

// shrink to three elements
array_splice($array, 3);

// remove last element, equivalent to array_pop( )
array_splice($array, -1);

// only remaining fruits are apple and banana
print_r($array);
Array
               (
                   [0] => apple
                   [1] => banana
               )
            

See Also

Documentation on array_pad( ) at http://www.php.net/array-pad and array_splice( ) at http://www.php.net/array-splice.

Appending One Array to Another

Problem

You want to combine two arrays into one.

Solution

Use array_merge( ):

$garden = array_merge($fruits, $vegetables);

Discussion

The array_merge( ) function works with both predefined arrays and arrays defined in place using array( ):

$p_languages = array('Perl', 'PHP');
$p_languages = array_merge($p_languages, array('Python'));
print_r($p_languages);
Array
               (
                   [0] => PHP
                   [1] => Perl
                   [2] => Python
               )
            

Accordingly, merged arrays can be either preexisting arrays, as with $p_languages, or anonymous arrays, as with array('Python').

You can't use array_push( ) , because PHP won't automatically flatten out the array into series of independent variables, and you'll end up with a nested array. Thus:

array_push($p_languages, array('Python'));
print_r($p_languages);
Array
               (
                   [0] => PHP
                   [1] => Perl
                   [2] => Array
                       (
                           [0] => Python
                       )

               )
            

Merging arrays with only numerical keys causes the arrays to get renumbered, so values aren't lost. Merging arrays with string keys causes the second array to overwrite the value of any duplicated keys. Arrays with both types of keys exhibit both types of behavior. For example:

$lc = array('a', 'b' => 'b'); // lower-case letters as values
$uc = array('A', 'b' => 'B'); // upper-case letters as values
$ac = array_merge($lc, $uc);  // all-cases?
print_r($ac);
Array
               (
                   [0] => a
                   [b] => B
                   [1] => A
               )
            

The uppercase A has been renumbered from index 0 to index 1, to avoid a collision, and merged onto the end. The uppercase B has overwritten the lowercase b and replaced it in the original place within the array.

The + operator can also merge arrays. The array on the right overwrites any identically named keys found on the left. It doesn't do any reordering to prevent collisions. Using the previous example:

print_r($a + $b);
print_r($b + $a);
Array
               (
                   [0] => a
                   [b] => b
               )
               Array
               (
                   [0] => A
                   [b] => B
               )
            

Since a and A both have a key of 0, and b and B both have a key of b, you end up with a total of only two elements in the merged arrays.

In the first case, $a + $b becomes just $b, and in the other, $b + $a becomes $a.

However, if you had two distinctly keyed arrays, this wouldn't be a problem, and the new array would be the union of the two arrays.

See Also

Documentation on array_merge( ) at http://www.php.net/array-merge.

Turning an Array into a String

Problem

You have an array, and you want to convert it into a nicely formatted string.

Solution

Use join( ):

// make a comma delimited list
$string = join(',', $array);

Or loop yourself:

$string = '';

foreach ($array as $key => $value) {
    $string .= ",$value";
}

$string = substr($string, 1); // remove leading ","

Discussion

If you can use join( ) , do; it's faster than any PHP-based loop. However, join( ) isn't very flexible. First, it places a delimiter only between elements, not around them. To wrap elements inside HTML bold tags and separate them with commas, do this:

$left  = '<b>';
$right = '</b>';

$html = $left . join("$right,$left", $html) . $right;

Second, join( ) doesn't allow you to discriminate against values. If you want to include a subset of entries, you need to loop yourself:

$string = '';

foreach ($fields as $key => $value) {
    // don't include password
    if ('password' != $key) {
        $string .= ",<b>$value</b>";
    }
}

$string = substr($string, 1); // remove leading ","

Notice that a separator is always added to each value, then stripped off outside the loop. While it's somewhat wasteful to add something that will be later subtracted, it's far cleaner and efficient (in most cases) then attempting to embed logic inside of the loop. To wit:

$string = '';
foreach ($fields as $key => $value) {
    // don't include password
    if ('password' != $value) {
        if (!empty($string)) { $string .= ','; }
        $string .= "<b>$value</b>";
    }
}

Now you have to check $string every time you append a value. That's worse than the simple substr( ) call. Also, prepend the delimiter (in this case a comma) instead of appending it because it's faster to shorten a string from the front than the rear.

See Also

Recipe 4.10 for printing an array with commas; documentation on join( ) at http://www.php.net/join and substr( ) at http://www.php.net/substr.

Printing an Array with Commas

Problem

You want to print out an array with commas separating the elements and with an "and" before the last element if there are more than two elements in the array.

Solution

Use the pc_array_to_comma_string( ) function shown in Example 4-1, which returns the correct string.

Example 4-1. pc_array_to_comma_string( )

function pc_array_to_comma_string($array) {

    switch (count($array)) {
    case 0:
        return '';

    case 1:
        return reset($array);
    
    case 2:
        return join(' and ', $array);

    default:
        $last = array_pop($array);
        return join(', ', $array) . ", and $last";
    }
}

Discussion

If you have a list of items to print, it's useful to print them in a grammatically correct fashion. It looks awkward to display text like this:

$thundercats = array('Lion-O', 'Panthro', 'Tygra', 'Cheetara', 'Snarf');
print 'ThunderCat good guys include ' . join(', ', $thundercats) . '.';
ThunderCat good guys include Lion-O, Panthro, Tygra, Cheetara, Snarf.

This implementation of this function isn't completely straightforward, since we want pc_array_to_comma_string( ) to work with all arrays, not just numeric ones beginning at 0. If restricted only to that subset, for an array of size one, you return $array[0]. But, if the array doesn't begin at 0, $array[0] is empty. So, you can use the fact that reset( ) , which resets an array's internal pointer, also returns the value of the first array element.

For similar reasons, you call array_pop( ) to grab the end element, instead of assuming it's located at $array[count($array)-1]. This allows you to use join( ) on $array.

Also note that the code for case 2 actually also works correctly for case 1. And, the default code works (though inefficiently) for case 2; however, the transitive property doesn't apply, so you can't use the default code on elements of size 1.

See Also

Recipe 4.9 for turning an array into a string; documentation on join( ) at http://www.php.net/join, array_pop( ) at http://www.php.net/array-pop, and reset( ) at http://www.php.net/reset.

Checking if a Key Is in an Array

Problem

You want to know if an array contains a certain key.

Solution

Use isset( ) :

if (isset($array['key'])) { /* there is a value for 'key' in $array */ }

Discussion

You can check the definedness of an array element just as you'd for any other variable. See the Introduction to Chapter 5 for more information about the truth value of variables.

See Also

Documentation on isset( ) at http://www.php.net/isset.

Checking if an Element Is in an Array

Problem

You want to know if an array contains a certain value.

Solution

Use in_array( ) :

if (in_array($value, $array)) {
    // an element has $value as its value in array $array
}

Discussion

Use in_array( ) to check if an element of an array holds a value:

$book_collection = array('Emma', 'Pride and Prejudice', 'Northhanger Abbey');
$book = 'Sense and Sensibility';

if (in_array($book, $book_collection) { 
    echo 'Own it.';
} else {
    echo 'Need it.';
}

The default behavior of in_array( ) is to compare items using the == operator. To use the strict equality check, ===, pass true as the third parameter to in_array( ):

$array = array(1, '2', 'three');

in_array(0, $array);        // true!
in_array(0, $array, true);  // false
in_array(1, $array);        // true
in_array(1, $array, true);  // true
in_array(2, $array);        // true
in_array(2, $array, true);  // false

The first check, in_array(0, $array), evaluates to true because to compare the number 0 against the string three, PHP casts three to an integer. Since three isn't a numeric string, as is 2, it becomes 0. Therefore, in_array( ) thinks there's a match.

Consequently, when comparing numbers against data that may contain strings, it's safest to use a strict comparison.

If you find yourself calling in_array( ) multiple times on the same array, it may be better to use an associative array, with the original array elements as the keys in the new associative array. Looking up entries using in_array( ) takes linear time; with an associative array, it takes constant time.

If you can't create the associative array directly but need to convert from a traditional one with integer keys, use array_flip( ) to swap the keys and values of an array:

$book_collection = array('Emma',
                         'Pride and Prejudice',
                         'Northhanger Abbey');

// convert from numeric array to associative array
$book_collection = array_flip($book_collection);
$book = 'Sense and Sensibility';

if (isset($book_collection[$book])) { 
    echo 'Own it.';
} else {
    echo 'Need it.';
}

Note that doing this condenses multiple keys with the same value into one element in the flipped array.

See Also

Recipe 4.13 for determining the position of an element in an array; documentation on in_array( ) at http://www.php.net/in-array and array_flip( ) at http://www.php.net/array-flip.

Finding the Position of an Element in an Array

Problem

You want to know if an element is in an array, and, if it is, you want to know where it is located.

Solution

Use array_search( ) . It returns the key of the found element or false:

$position = array_search($value, $array);
if ($position !== false) {
    // the element in position $position has $value as its value in array $array
}

Discussion

Use in_array( ) to find if an array contains a value; use array_search( ) to discover where that value is located. However, because array_search( ) gracefully handles searches in which the value isn't found, it's better to use array_search( ) instead of in_array( ). The speed difference is minute, and the extra information is potentially useful:

$favorite_foods = array(1 => 'artichokes', 'bread', 'cauliflower', 'deviled eggs');
$food = 'cauliflower';
$position = array_search($food, $favorite_foods);

if ($position !== false) {
    echo "My #$position favorite food is $food";
} else {
    echo "Blech! I hate $food!";
}

Use the !== check against false because if your string is found in the array at position 0, the if evaluates to a logical false, which isn't what is meant or wanted.

If a value is in the array multiple times, array_search() is only guaranteed to return one of the instances, not the first instance.

See Also

Recipe 4.12 for checking whether an element is in an array; documentation on array_search( ) at http://www.php.net/array-search; for more sophisticated searching of arrays using regular expression, see preg_replace( ) at http://www.php.net/preg-replace and Chapter 13.

Finding Elements That Pass a Certain Test

Problem

You want to locate entries in an array that meet certain requirements.

Solution

Use a foreach loop:

$movies = array(...);

foreach ($movies as $movie) {
    if ($movie['box_office_gross'] < 5000000) { $flops[] = $movie; }
}

Or array_filter( ) :

$movies = array(...);

function flops($movie) {
    return ($movie['box_office_gross'] < 5000000) ? 1 : 0;
}

$flops = array_filter($movies, 'flops');

Discussion

The foreach loops are simple; you scroll through the data and append elements to the return array that match your criteria.

If you want only the first such element, exit the loop using break :

foreach ($movies as $movie) {
    if ($movie['box_office_gross'] > 200000000) { $blockbuster = $movie; break; }
}

You can also return directly from a function:

function blockbuster($movies) {
    foreach ($movies as $movie) {
        if ($movie['box_office_gross'] > 200000000) { return $movie; }
    }
}

With array_filter( ) , however, you first create a callback function that returns true for values you want to keep and false for values you don't. Using array_filter( ), you then instruct PHP to process the array as you do in the foreach.

It's impossible to bail out early from array_filter( ), so foreach provides more flexibility and is simpler to understand. Also, it's one of the few cases in which the built-in PHP function doesn't clearly outperform user-level code.

See Also

Documentation on array_filter( ) at http://www.php.net/array-filter.

Finding the Largest or Smallest Valued Element in an Array

Problem

You have an array of elements, and you want to find the largest or smallest valued element. For example, you want to find the appropriate scale when creating a histogram.

Solution

To find the largest element, use max( ) :

$largest = max($array);

To find the smallest element, use min( ) :

$smallest = min($array);

Discussion

Normally, max( ) returns the larger of two elements, but if you pass it an array, it searches the entire array instead. Unfortunately, there's no way to find the index of the largest element using max( ). To do that, you must sort the array in reverse order to put the largest element in position 0:

arsort($array);

Now the value of the largest element is $array[0].

If you don't want to disturb the order of the original array, make a copy and sort the copy:

$copy = $array;
arsort($copy);

The same concept applies to min( ) but use asort( ) instead of arsort( ).

See Also

Recipe 4.17 for sorting an array; documentation on max( ) at http://www.php.net/max, min( ) at http://www.php.net/min, arsort( ) at http://www.php.net/arsort, and asort( ) at http://www.php.net/min.

Reversing an Array

Problem

You want to reverse the order of the elements in an array.

Solution

Use array_reverse( ) :

$array = array('Zero', 'One', 'Two');
$reversed = array_reverse($array);

Discussion

The array_reverse( ) function reverses the elements in an array. However, it's often possible to avoid this operation. If you wish to reverse an array you've just sorted, modify the sort to do the inverse. If you want to reverse a list you're about to loop through and process, just invert the loop. Instead of:

for ($i = 0, $size = count($array); $i < $size; $i++) {
    ...
}

do the following:

for ($i = count($array) - 1; $i >=0 ; $i--) { 
    ...
}

However, as always, use a for loop only on a tightly packed array.

Another alternative would be, if possible, to invert the order elements are placed into the array. For instance, if you're populating an array from a series of rows returned from a database, you should be able to modify the query to ORDER DESC. See your database manual for the exact syntax for your database.

See Also

Documentation on array_reverse( ) at http://www.php.net/array-reverse.

Sorting an Array

Problem

You want to sort an array in a specific way.

Solution

To sort an array using the traditional definition of sort, use sort( ) :

$states = array('Delaware', 'Pennsylvania', 'New Jersey');
sort($states);

To sort numerically, pass SORT_NUMERIC as the second argument to sort( ).

$scores = array(1, 10, 2, 20);
sort($scores, SORT_NUMERIC);

This resorts the numbers in ascending order (1, 2, 10, 20) instead of lexicographical order (1, 10, 2, 20).

Discussion

The sort( ) function doesn't preserve the key/value association between elements; instead, entries are reindexed starting at 0 and going upward. (The one exception to this rule is a one-element array; its lone element doesn't have its index reset to 0. This is fixed as of PHP 4.2.3.)

To preserve the key/value links, use asort( ). The asort( ) function is normally used for associative arrays, but it can also be useful when the indexes of the entries are meaningful:

$states = array(1 => 'Delaware', 'Pennsylvania', 'New Jersey');
asort($states);

while (list($rank, $state) = each($states)) {
    print "$state was the #$rank state to join the United States\n";

}

Use natsort( ) to sort the array using a natural sorting algorithm. Under natural sorting, you can mix strings and numbers inside your elements and still get the right answer.

$tests = array('test1.php', 'test10.php', 'test11.php', 'test2.php');
natsort($tests);

The elements are now ordered: 'test1.php', 'test2.php', 'test10.php', and 'test11.php'. With natural sorting, the number 10 comes after the number 2; the opposite occurs under traditional sorting. For case-insensitive natural sorting, use natcasesort( ).

To sort the array in reverse order, use rsort( ) or arsort( ), which is like rsort( ) but also preserves keys. There is no natrsort( ) or natcasersort( ). You can also pass SORT_NUMERIC into these functions.

See Also

Recipe 4.18 for sorting with a custom comparison function and Recipe 4.19 for sorting multiple arrays; documentation on sort( ) at http://www.php.net/sort, asort( ) at http://www.php.net/asort, natsort( ) at http://www.php.net/natsort, natcasesort( ) at http://www.php.net/natcasesort, rsort( ) at http://www.php.net/rsort, and arsort( ) at http://www.php.net/arsort.

Sorting an Array by a Computable Field

Problem

You want to define your own sorting routine.

Solution

Use usort( ) in combination with a custom comparison function:

// sort in reverse natural order
function natrsort($a, $b) {
    return strnatcmp($b, $a);
}

$tests = array('test1.php', 'test10.php', 'test11.php', 'test2.php');
usort($tests, 'natrsort');

Discussion

The comparison function must return a value greater that 0 if $a > $b, 0 if $a == $b, and a value less than 0 if $a < $b. To sort in reverse, do the opposite. The function in the Solution, strnatcmp( ) , obeys those rules.

To reverse the sort, instead of multiplying the return value of strnatcmp($a, $b) by -1, switch the order of the arguments to strnatcmp($b, $a).

The sort function doesn't need to be a wrapper for an existing sort. For instance, the pc_date_sort( ) function, shown in Example 4-2, shows how to sort dates.

Example 4-2. pc_date_sort( )

// expects dates in the form of "MM/DD/YYYY"
function pc_date_sort($a, $b) {
    list($a_month, $a_day, $a_year) = explode('/', $a);
    list($b_month, $b_day, $b_year) = explode('/', $b);

    if ($a_year  > $b_year ) return  1;
    if ($a_year  < $b_year ) return -1;

    if ($a_month > $b_month) return  1;
    if ($a_month < $b_month) return -1;

    if ($a_day   > $b_day  ) return  1;
    if ($a_day   < $b_day  ) return -1;

    return 0;
}

$dates = array('12/14/2000', '08/10/2001', '08/07/1999');
usort($dates, 'pc_date_sort');

While sorting, usort( ) frequently recomputes the sort function's return values each time it's needed to compare two elements, which slows the sort. To avoid unnecessary work, you can cache the comparison values, as shown in pc_array_sort( ) in Example 4-3.

Example 4-3. pc_array_sort( )

function pc_array_sort($array, $map_func, $sort_func = '') {
    $mapped = array_map($map_func, $array);    // cache $map_func( ) values

    if ('' == $sort_func) { 
        asort($mapped);                        // asort( ) is faster then usort( )
    }  else { 
        uasort($mapped, $sort_func);           // need to preserve keys
    }

    while (list($key) = each($mapped)) {
        $sorted[ ] = $array[$key];              // use sorted keys
    }

    return $sorted;
}

To avoid unnecessary work, pc_array_sort( ) uses a temporary array, $mapped, to cache the return values. It then sorts $mapped, using either the default sort order or a user-specified sorting routine. Importantly, it uses a sort that preserves the key/value relationship. By default, it uses asort( ) because asort( ) is faster than uasort( ). (Slowness in uasort( ) is the whole reason for pc_array_sort( ) after all.) Finally, it creates a sorted array, $sorted, using the sorted keys in $mapped to index the values in the original array.

For small arrays or simple sort functions, usort( ) is faster, but as the number of computations grows, pc_array_sort( ) surpasses usort( ). The following example sorts elements by their string lengths — a relatively quick custom sort:

function pc_u_length($a, $b) {
    $a = strlen($a);
    $b = strlen($b);

    if ($a == $b) return  0;
    if ($a  > $b) return  1;
                  return -1;
}

function pc_map_length($a) {
    return strlen($a);
}

$tests = array('one', 'two', 'three', 'four', 'five',
               'six', 'seven', 'eight', 'nine', 'ten');

// faster for < 5 elements using pc_u_length()
usort($tests, 'pc_u_length');

// faster for >= 5 elements using pc_map_length()
$tests = pc_array_sort($tests, 'pc_map_length');

Here, pc_array_sort( ) is faster than usort( ) once the array reaches five elements.

See Also

Recipe 4.17 for basic sorting and Recipe 4.19 for sorting multiple arrays; documentation on usort( ) at http://www.php.net/usort, asort( ) at http://www.php.net/asort, and array_map( ) at http://www.php.net/array-map.

Sorting Multiple Arrays

Problem

You want to sort multiple arrays or an array with multiple dimensions.

Solution

Use array_multisort( ) :

To sort multiple arrays simultaneously, pass multiple arrays to array_multisort( ):

$colors = array('Red', 'White', 'Blue');
$cities = array('Boston', 'New York', 'Chicago');

array_multisort($colors, $cities);
print_r($colors);
print_r($cities);
Array
               (
                   [0] => Blue
                   [1] => Red
                   [2] => White
               )
               Array
               (
                   [0] => Chicago
                   [1] => Boston
                   [2] => New York
               )
            

To sort multiple dimensions within a single array, pass the specific array elements:

$stuff = array('colors' => array('Red', 'White', 'Blue'),
               'cities' => array('Boston', 'New York', 'Chicago'));

array_multisort($stuff['colors'], $stuff['cities']);
print_r($stuff);
Array
               (
                   [colors] => Array
                       (
                           [0] => Blue
                           [1] => Red
                           [2] => White
                       )

                   [cities] => Array
                       (
                           [0] => Chicago
                           [1] => Boston
                           [2] => New York
                       )

               )
            

To modify the sort type, as in sort( ), pass in SORT_REGULAR, SORT_NUMERIC, or SORT_STRING after the array. To modify the sort order, unlike in sort( ), pass in SORT_ASC or SORT_DESC after the array. You can also pass in both a sort type and a sort order after the array.

Discussion

The array_multisort( ) function can sort several arrays at once or a multidimensional array by one or more dimensions. The arrays are treated as columns of a table to be sorted by rows. The first array is the main one to sort by; all the items in the other arrays are reordered based on the sorted order of the first array. If items in the first array compare as equal, the sort order is determined by the second array, and so on.

The default sorting values are SORT_REGULAR and SORT_ASC, and they're reset after each array, so there's no reason to pass either of these two values, except for clarity.

$numbers = array(0, 1, 2, 3);
$letters = array('a', 'b', 'c', 'd');
array_multisort($numbers, SORT_NUMERIC, SORT_DESC,
                $letters, SORT_STRING , SORT_DESC);

This example reverses the arrays.

See Also

Recipe 4.17 for simple sorting and Recipe 4.18 for sorting with a custom function; documentation on array_multisort( ) at http://www.php.net/array-multisort.

Sorting an Array Using a Method Instead of a Function

Problem

You want to define a custom sorting routine to order an array. However, instead of using a function, you want to use an object method.

Solution

Pass in an array holding a class name and method in place of the function name:

usort($access_times, array('dates', 'compare'));

Discussion

As with a custom sort function, the object method needs to take two input arguments and return 1, 0, or -1, depending if the first parameter is larger than, equal to, or less than the second:

class pc_sort {
    // reverse-order string comparison
    function strrcmp($a, $b) {
        return strcmp($b, $a);
    }
}

usort($words, array('pc_sort', 'strrcmp'));

See Also

Chapter 7 for more on classes and objects; Recipe 4.18 for more on custom sorting of arrays.

Randomizing an Array

Problem

You want to scramble the elements of an array in a random order.

Solution

If you're running PHP 4.3 or above, use shuffle( ) :

shuffle($array);

If you're running an earlier version, use the pc_array_shuffle( ) function shown in Example 4-4.

Example 4-4. pc_array_shuffle( )

function pc_array_shuffle($array) {
    $i = count($array);

    while(--$i) {
        $j = mt_rand(0, $i);

        if ($i != $j) {
            // swap elements
            $tmp = $array[$j];
            $array[$j] = $array[$i];
            $array[$i] = $tmp;
        }
    }

    return $array;
}

Here's an example:

$cards = range(1,52); // deal out 52 "cards"
$cards = pc_array_shuffle($cards);

Discussion

There's already a shuffle( ) function in PHP to shuffle arrays, but as of PHP 4.2.2, it doesn't do its job correctly. The built-in shuffling algorithm tends to favor certain permutations more than others. Elements end up looking randomized, but since each element doesn't have the same chance of ending up in each position, it's not a true shuffle. This is fixed in PHP 4.3.

pc_array_shuffle( ) , known as the Fisher-Yates shuffle, equally distributes the elements throughout the array. Use it if you run a version of PHP earlier than 4.3. Unlike shuffle( ), this function returns the scrambled array instead of modifying it in-place. It also requires a tightly packed array with integer keys.

See Also

Recipe 4.22 for a function that simulates shuffling a deck of cards; documentation on shuffle( ) at http://www.php.net/shuffle.

Shuffling a Deck of Cards

Problem

You want to shuffle a deck of cards and deal them out.

Solution

Create a array of 52 integers, shuffle them, and map them to cards:

$suits = array('Clubs', 'Diamonds', 'Hearts', 'Spades');
$cards = array('Ace', 2, 3, 4, 5, 6, 7, 8, 9, 10, 'Jack', 'Queen', 'King');

$deck = pc_array_shuffle(range(0, 51));

while (($draw = array_pop($deck)) != NULL) {
    print  $cards[$draw / 4] . ' of ' . $suits[$draw % 4] . "\n";
}

This code uses the pc_array_shuffle( ) function from Recipe 4.21.

Discussion

Here, a pair of arrays, $suits and $cards, is created to hold the English representation of a card. The numbers 0 through 51 are randomly arranged and assigned to $deck. To deal a card, just pop them off the top of the array, treating the array like a literal deck of cards.

It's necessary to add the check against NULL inside the while, otherwise the loop terminates when you draw the zeroth card. If you modify the deck to contain the numbers 1 through 52, the mathematics of deciding which number belongs to which card becomes more complex.

To deal multiple cards at once, call array_slice( ):

array_slice($deck, $cards * -1);

See Also

Recipe 4.21 for a function that randomizes an array; documentation on array_slice( ) at http://www.php.net/array-slice.

Removing Duplicate Elements from an Array

Problem

You want to eliminate duplicates from an array.

Solution

If the array is already complete, use array_unique( ) , which returns a new array that contains no duplicate values:

$unique = array_unique($array);

If you create the array while processing results, here is a technique for numerical arrays:

foreach ($_REQUEST['fruits'] as $fruit) {
    if (!in_array($array, $fruit)) { $array[ ] = $fruit; }
}

Here's one for associative arrays:

foreach ($_REQUEST['fruits'] as $fruit) {
    $array[$fruit] = $fruit;
}

Discussion

Once processing is completed, array_unique( ) is the best way to eliminate duplicates. But, if you're inside a loop, you can eliminate the duplicate entries from appearing by checking if they're already in the array.

An even faster method than using in_array( ) is to create a hybrid array in which the key and the value for each element are the same. This eliminates the linear check of in_array( ) but still allows you to take advantage of the array family of functions that operate over the values of an array instead of the keys.

In fact, it's faster to use the associative array method and then call array_values( ) on the result (or, for that matter, array_keys( ) , but array_values( ) is slightly faster) than to create a numeric array directly with the overhead of in_array( ).

See Also

Documentation on array_unique( ) at http://www.php.net/array-unique.

Finding the Union, Intersection, or Difference of Two Arrays

Problem

You have a pair of arrays, and you want to find their union (all the elements), intersection (elements in both, not just one), or difference (in one but not both).

Solution

To compute the union:

$union = array_unique(array_merge($a, $b));

To compute the intersection:

$intersection = array_intersect($a, $b);

To find the simple difference:

$difference = array_diff($a, $b);

And for the symmetric difference:

$difference = array_merge(array_diff($a, $b), array_diff($b, $a));

Discussion

Many necessary components for these calculations are built into PHP, it's just a matter of combining them in the proper sequence.

To find the union, you merge the two arrays to create one giant array with all values. But, array_merge( ) allows duplicate values when merging two numeric arrays, so you call array_unique( ) to filter them out. This can leave gaps between entries because array_unique( ) doesn't compact the array. It isn't a problem, however, as foreach and each( ) handle sparsely filled arrays without a hitch.

The function to calculate the intersection is simply named array_intersection( ) and requires no additional work on your part.

The array_diff( ) function returns an array containing all the unique elements in $old that aren't in $new. This is known as the simple difference:

$old = array('To', 'be', 'or', 'not', 'to', 'be');
$new = array('To', 'be', 'or', 'whatever');
$difference = array_diff($old, $new);
Array
               (
                   [3] => not
                   [4] => to
               )
            

The resulting array, $difference contains 'not' and 'to', because array_diff( ) is case-sensitive. It doesn't contain 'whatever' because it doesn't appear in $old.

To get a reverse difference, or in other words, to find the unique elements in $new that are lacking in $old, flip the arguments:

$old = array('To', 'be', 'or', 'not', 'to', 'be');
$new = array('To', 'be', 'or', 'whatever');
$reverse_diff = array_diff($new, $old);
Array
               (
                   [3] => whatever
               )
            

The $reverse_diff array contains only 'whatever'.

If you want to apply a function or other filter to array_diff( ), roll your own diffing algorithm:

// implement case-insensitive diffing; diff -i

$seen = array( );
foreach ($new as $n) {
    $seen[strtolower($n)]++;
}

foreach ($old as $o) {
    $o = strtolower($o);
    if (!$seen[$o]) { $diff[$o] = $o; }
}

The first foreach builds an associative array lookup table. You then loop through $old and, if you can't find an entry in our lookup, add the element to $diff.

It can be a little faster to combine array_diff( ) with array_map( ):

$diff = array_diff(array_map('strtolower', $old), array_map('strtolower', $new));

The symmetric difference is what's in $a, but not $b, and what's in $b, but not $a:

$difference = array_merge(array_diff($a, $b), array_diff($b, $a));

Once stated, the algorithm is straightforward. You call array_diff( ) twice and find the two differences. Then you merge them together into one array. There's no need to call array_unique( ), since you've intentionally constructed these arrays to have nothing in common.

See Also

Documentation on array_unique( ) at http://www.php.net/array-unique, array_intersect( ) at http://www.php.net/array-intersect, array_diff( ) at http://www.php.net/array-diff, array_merge( ) at http://www.php.net/array-merge, and array_map( ) at http://www.php.net/array-map.

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, 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.

See Also

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

Finding All Permutations of an Array

Problem

You have an array of elements and want to compute all the different ways they can be ordered.

Solution

Use one of the two permutation algorithms discussed next.

Discussion

The pc_permute() function shown in Example 4-6 is a PHP modification of a basic recursive function.

Example 4-6. pc_permute( )

function pc_permute($items, $perms = array( )) {
    if (empty($items)) { 
        print join(' ', $perms) . "\n";
    }  else {
        for ($i = count($items) - 1; $i >= 0; --$i) {
             $newitems = $items;
             $newperms = $perms;
             list($foo) = array_splice($newitems, $i, 1);
             array_unshift($newperms, $foo);
             pc_permute($newitems, $newperms);
         }
    }
}

For example:

pc_permute(split(' ', 'she sells seashells'));
she sells seashells
               she seashells sells
               sells she seashells
               sells seashells she
               seashells she sells
               seashells sells she
            

However, while this recursion is elegant, it's inefficient, because it's making copies all over the place. Also, it's not easy to modify the function to return the values instead of printing them out without resorting to a global variable.

The pc_next_permutation( ) function shown in Example 4-7, however, is a little slicker. It combines an idea of Mark-Jason Dominus from Perl Cookbook by Tom Christianson and Nathan Torkington (O'Reilly) with an algorithm from Edsger Dijkstra's classic text A Discipline of Programming (Prentice-Hall).

Example 4-7. pc_next_permutation( )

function pc_next_permutation($p, $size) {
    // slide down the array looking for where we're smaller than the next guy
    for ($i = $size - 1; $p[$i] >= $p[$i+1]; --$i) { }

    // if this doesn't occur, we've finished our permutations
    // the array is reversed: (1, 2, 3, 4) => (4, 3, 2, 1)
    if ($i == -1) { return false; }

    // slide down the array looking for a bigger number than what we found before
    for ($j = $size; $p[$j] <= $p[$i]; --$j) { }

    // swap them
    $tmp = $p[$i]; $p[$i] = $p[$j]; $p[$j] = $tmp;

    // now reverse the elements in between by swapping the ends
    for (++$i, $j = $size; $i < $j; ++$i, --$j) {
         $tmp = $p[$i]; $p[$i] = $p[$j]; $p[$j] = $tmp;
    }

    return $p;
}

$set = split(' ', 'she sells seashells'); // like array('she', 'sells', 'seashells')
$size = count($set) - 1;
$perm = range(0, $size);
$j = 0;

do { 
     foreach ($perm as $i) { $perms[$j][] = $set[$i]; }
} while ($perm = pc_next_permutation($perm, $size) and ++$j);

foreach ($perms as $p) {
    print join(' ', $p) . "\n";
}

Dominus's idea is that instead of manipulating the array itself, you can create permutations of integers. You then map the repositioned integers back onto the elements of the array to calculate the true permutation — a nifty idea.

However, this technique still has some shortcomings. Most importantly, to us as PHP programmers, it frequently pops, pushes, and splices arrays, something that's very Perl-centric. Next, when calculating the permutation of integers, it goes through a series of steps to come up with each permutation; because it doesn't remember previous permutations, it therefore begins each time from the original permutation. Why redo work if you can help it?

Dijkstra's algorithm solves this by taking a permutation of a series of integers and returning the next largest permutation. The code is optimized based upon that assumption. By starting with the smallest pattern (which is just the integers in ascending order) and working your way upwards, you can scroll through all permutations one at a time, by plugging the previous permutation back into the function to get the next one. There are hardly any swaps, even in the final swap loop in which you flip the tail.

There's a side benefit. Dominus's recipe needs the total number of permutations for a given pattern. Since this is the factorial of the number of elements in the set, that's a potentially expensive calculation, even with memoization. Instead of computing that number, it's faster to return false from pc_next_permutation( ) when you notice that $i == -1. When that occurs, you're forced outside the array, and you've exhausted the permutations for the phrase.

Two final notes of implementation. Since the size of the set is invariant, you capture it once using count( ) and pass it into pc_next_permutation( ); this is faster than repeatedly calling count( ) inside the function. Also, since the set is guaranteed by its construction to have unique elements, i.e., there is one and only one instance of each integer, we don't need to need to check for equality inside the first two for loops. However, you should include them in case you want to use this recipe on other numeric sets, in which duplicates might occur.

See Also

Recipe 4.25 for a function that finds the power set of an array; Recipe 4.19 in the Perl Cookbook (O'Reilly); Chapter 3, A Discipline of Programming (Prentice-Hall).

Program: Printing an Array in a Horizontally Columned HTML Table

Converting an array into a horizontally columned table places a fixed number of elements in a row. The first set goes in the opening table row, the second set goes in the next row, and so forth. Finally, you reach the final row, where you might need to optionally pad the row with empty table data cells.

The function pc_grid_horizontal( ) , shown in Example 4-8, lets you specify an array and number of columns. It assumes your table width is 100%, but you can alter the $table_width variable to change this.

Example 4-8. pc_grid_horizontal( )

function pc_grid_horizontal($array, $size) {

    // compute <td> width %ages
    $table_width = 100;
    $width = intval($table_width / $size);

    // define how our <tr> and <td> tags appear
    // sprintf() requires us to use %% to get literal %
    $tr = '<tr align="center">';
    $td = "<td width=\"$width%%\">%s</td>";

    // open table
    $grid = "<table width=\"$table_width%\">$tr";

    // loop through entries and display in rows of size $sized
    // $i keeps track of when we need a new table tow
    $i = 0;
    foreach ($array as $e) {
        $grid .= sprintf($td, $e);
        $i++;

        // end of a row
        // close it up and open a new one
        if (!($i % $size)) {
            $grid .= "</tr>$tr";
        }
    }

    // pad out remaining cells with blanks
    while ($i % $size) {
        $grid .= sprintf($td, '&nbsp;');
        $i++;
    }

    // add </tr>, if necessary
    $end_tr_len = strlen($tr) * -1;
    if (substr($grid, $end_tr_len) != $tr) {
        $grid .= '</tr>';
    } else {
        $grid = substr($grid, 0, $end_tr_len);
    }

    // close table
    $grid .= '</table>';

    return $grid;
}

The function begins by calculating the width of each <td> as a percentage of the total table size. Depending on the number of columns and the overall size, the sum of the <td> widths might not equal the <table> width, but this shouldn't effect the displayed HTML in a noticeable fashion. Next, define the <td> and <tr> tags, using printf-style formatting notation. To get the literal % needed for the <td> width percentage, use a double %%.

The meat of the function is the foreach loop through the array in which we append each <td> to the $grid. If you reach the end of a row, which happens when the total number of elements processed is a multiple of number of elements in a row, you close and then reopen the <tr>.

Once you finish adding all the elements, you need to pad the final row with blank or empty <td> elements. Put a nonbreaking space inside the data cell instead of leaving it empty to make the table renders properly in the browser. Now, make sure there isn't an extra <tr> at the end of grid, which occurs when the number of elements is an exact multiple of the width (in other words, if you didn't need to add padding cells). Finally, you can close the table.

For example, let's print the names of the 50 U.S. states in a six-column table:

// establish connection to database
$dsn = 'mysql://user:password@localhost/table';
$dbh = DB::connect($dsn);
if (DB::isError($dbh)) { die ($dbh->getMessage( )); }

// query the database for the 50 states
$sql = "SELECT state FROM states";
$sth = $dbh->query($sql);

// load data into array from database
while ($row = $sth->fetchRow(DB_FETCHMODE_ASSOC)) {
  $states[ ] = $row['state'];
}

// generate the HTML table
$grid = pc_grid_horizontal($states, 6);

// and print it out
print $grid;

When rendered in a browser, it looks like Figure 4-1.

Figure 4-1. The United States of America

The United States of America

Because 50 doesn't divide evenly by six, there are four extra padding cells in the last row.

Notes

  1. John Tyler was elected as Harrison's Vice President under the Whig Party platform but was expelled from the party shortly after assuming the presidency following the death of Harrison.
Personal tools