Wie generiert man alle String-Permutationen mithilfe von Backtracking in PHP?

Permutationen einer Zeichenfolge mithilfe eines Backtracking-Ansatzes

Permutation bezieht sich auf die Neuanordnung der Zeichen einer Zeichenfolge in allen möglichen Reihenfolgen. Um alle Permutationen einer Zeichenfolge in PHP zu generieren, können wir einen Backtracking-Algorithmus verwenden.

Angenommen, wir haben eine Zeichenfolge „hey“.

1. Teilen Sie die Zeichenfolge auf in einzelne Zeichen:

   Wir beginnen mit der Aufteilung der Zeichenfolge in ein Array einzelner Zeichen. In diesem Fall ['h', 'e', ​​'y'].

2. Permutationen rekursiv generieren:

   Mit Rekursion erstellen wir Generieren Sie Permutationen, indem Sie systematisch Zeichen austauschen und alle möglichen generieren Kombinationen.

3. Zurückgehen, um die ursprüngliche Reihenfolge wiederherzustellen:

   Nachdem wir eine Permutation generiert haben, gehen wir zurück, um die ursprüngliche Reihenfolge der Zeichen wiederherzustellen. Dies verhindert, dass doppelte Permutationen generiert werden.

Codebeispiel:

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

Ausgabe:

hey
hye
ehy
eyh
yeh
yhe

Dieser Backtracking-Ansatz stellt sicher, dass alle Permutationen systematisch generiert und gedruckt werden.

Das obige ist der detaillierte Inhalt vonWie generiert man alle String-Permutationen mithilfe von Backtracking in PHP?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!