How to Generate All String Permutations Using Backtracking in PHP?

Permutations of a String using a Backtracking Approach

Permutation refers to rearranging the characters of a string in all possible orders. To generate all permutations of a string in PHP, we can employ a backtracking algorithm.

Suppose we have a string "hey".

1. Split the String into Individual Characters:

   We begin by splitting the string into an array of individual characters. In this case, ['h', 'e', 'y'].

2. Recursively Generate Permutations:

   Using recursion, we generate permutations by systematically swapping characters and generating all possible combinations.

3. Backtrack to Restore Original Order:

   After generating a permutation, we backtrack to restore the original order of characters. This prevents duplicate permutations from being generated.

Code Example:

// Function to generate and print all permutations of $str (N = strlen($str)).
function permute($str, $i, $n) {
    if ($i == $n) {
        print "$str\n";
    } else {
        for ($j = $i; $j < $n; $j++) {
            swap($str, $i, $j);
            permute($str, $i + 1, $n);
            swap($str, $i, $j); // Backtrack.
        }
    }
}

// Function to swap the characters at positions $i and $j of $str.
function swap(&$str, $i, $j) {
    $temp = $str[$i];
    $str[$i] = $str[$j];
    $str[$j] = $temp;
}

$str = "hey";
permute($str, 0, strlen($str)); // Call the function.

Output:

hey
hye
ehy
eyh
yeh
yhe

This backtracking approach ensures all permutations are systematically generated and printed.

The above is the detailed content of How to Generate All String Permutations Using Backtracking in PHP?. For more information, please follow other related articles on the PHP Chinese website!