Wie kann ich mit rekursiven und iterativen Ansätzen alle möglichen Permutationen eines String-Arrays in PHP generieren?

Generieren von Array-Permutationen in PHP

Gegeben ein Array von Zeichenfolgen, wie zum Beispiel ['peter', 'paul', 'mary'] Die Aufgabe besteht darin, alle möglichen Permutationen seiner Elemente zu finden. Bei Permutationen werden die Elemente so neu angeordnet, dass ihre Identität erhalten bleibt. Die gewünschte Ausgabe wäre:

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

Lösung 1: Verwendung einer rekursiven Funktion

Eine rekursive Funktion kann verwendet werden, um Permutationen zu generieren, indem jedes Element aus dem ausgewählt und die Auswahl aufgehoben wird Array. Die folgende Funktion pc_permute untersucht alle möglichen Kombinationen:

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

Diese Funktion benötigt zwei Parameter: $items (das Eingabearray) und $perms (ein optionaler Parameter zum Verfolgen der aktuellen Permutation). Es durchläuft die Elemente in $items, entfernt eines, fügt es am Anfang von $perms hinzu und ruft sich dann selbst rekursiv mit den geänderten Argumenten auf. Wenn das Eingabearray leer wird, gibt die Funktion die aktuelle Permutation aus.

Lösung 2: Iterative Funktion verwenden

Alternativ kann ein iterativer Ansatz zum Generieren von Permutationen verwendet werden. Die Funktion pc_next_permutation führt die folgenden Schritte aus:

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

Diese Funktion benötigt zwei Parameter: $p (das Eingabearray) und $size (die Länge des Eingabearrays). Es durchläuft das Array in umgekehrter Reihenfolge und sucht nach einem Wert, der kleiner als das nächste Element ist. Wenn kein solcher Wert gefunden wird, bedeutet dies, dass die aktuelle Permutation die letzte ist. Andernfalls tauscht es den Wert mit dem nächstgrößeren aus und kehrt dann die verbleibenden Elemente in der Permutation um.

Durch den iterativen Aufruf von pc_next_permutation auf einem sortierten Array können alle möglichen Permutationen generiert werden. Der folgende Code demonstriert diesen Ansatz:

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

Das obige ist der detaillierte Inhalt vonWie kann ich mit rekursiven und iterativen Ansätzen alle möglichen Permutationen eines String-Arrays in PHP generieren?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!