How can I generate all possible permutations of an array of strings in PHP using both recursive and iterative approaches?

Generating Array Permutations in PHP

Given an array of strings, such as ['peter', 'paul', 'mary'], the task is to find all possible permutations of its elements. Permutations involve rearranging the elements in a way that preserves their identity. The desired output would be:

peter-paul-mary
peter-mary-paul
paul-peter-mary
paul-mary-peter
mary-peter-paul
mary-paul-peter

Solution 1: Using Recursive Function

A recursive function can be utilized to generate permutations by selecting and unselecting each element from the array. The pc_permute function below explores all possible combinations:

function pc_permute($items, $perms = array()) {
    if (empty($items)) { 
        echo join(' ', $perms) . "<br />";
    } 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);
         }
    }
}

This function takes two parameters: $items (the input array) and $perms (an optional parameter for keeping track of the current permutation). It iterates through the elements in $items, removes one, adds it to the beginning of $perms, and then calls itself recursively with the modified arguments. When the input array becomes empty, the function prints the current permutation.

Solution 2: Using Iterative Function

Alternatively, an iterative approach can be used to generate permutations. The pc_next_permutation function performs the following steps:

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;
}

This function takes two parameters: $p (the input array) and $size (the length of the input array). It iterates through the array in reverse order, looking for a value that is less than the next element. If no such value is found, it means that the current permutation is the last one. Otherwise, it swaps the value with the next larger one and then reverses the remaining elements in the permutation.

By calling pc_next_permutation iteratively on a sorted array, all possible permutations can be generated. The following code demonstrates this approach:

$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";
}

The above is the detailed content of How can I generate all possible permutations of an array of strings in PHP using both recursive and iterative approaches?. For more information, please follow other related articles on the PHP Chinese website!