Wie kann ich mit einem rekursiven Algorithmus alle Kombinationen einer bestimmten Menge in PHP generieren?

Generieren aller Kombinationen mithilfe des Algorithmus in PHP

Eine der grundlegenden Aufgaben in der Informatik ist das Generieren von Kombinationen aus einer gegebenen Menge. In diesem Zusammenhang bezieht sich eine Kombination auf eine Teilmenge von Elementen aus der ursprünglichen Menge mit einer bestimmten Größe.

Betrachten Sie beispielsweise eine Menge A = {A, B, C}. So können wir Kombinationen unterschiedlicher Größe erhalten:

Kombinationen mit einem rekursiven Algorithmus erzeugen

Um dieses Problem zu lösen, können wir einen rekursiven Algorithmus verwenden, der alle möglichen Kombinationen untersucht . Hier ist eine schrittweise Aufschlüsselung:

1. Initialisieren Sie ein leeres Array $combinations, um die Kombinationen zu speichern.
2. Wenn $size gleich 1 ist, haben wir den Basisfall erreicht und kann $kombinationen zurückgeben.
3. Durchlaufen Sie die $chars und den Strom $combinations.
4. Fügen Sie für jede Kombination und jedes Zeichen das Zeichen an die Kombination an und fügen Sie die neue Kombination zu $new_combinations hinzu.
5. Rufen Sie die Sampling-Funktion rekursiv mit aktualisierten $new_combinations auf und dekrementieren Sie $size um 1.

Umsetzung in PHP

function sampling($chars, $size, $combinations = []) {
    if (empty($combinations)) {
        $combinations = $chars;
    }
    if ($size == 1) {
        return $combinations;
    }
    $new_combinations = [];
    foreach ($combinations as $combination) {
        foreach ($chars as $char) {
            $new_combinations[] = $combination . $char;
        }
    }
    return sampling($chars, $size - 1, $new_combinations);
}

Beispiel

Betrachten wir unsere ursprüngliche Menge A = {A, B, C}.

$chars = ['A', 'B', 'C'];
$output = sampling($chars, 2);
var_dump($output);

Ausgabe

array(9) {
  [0]=>
  string(2) "AA"
  [1]=>
  string(2) "AB"
  [2]=>
  string(2) "AC"
  [3]=>
  string(2) "BA"
  [4]=>
  string(2) "BB"
  [5]=>
  string(2) "BC"
  [6]=>
  string(2) "CA"
  [7]=>
  string(2) "CB"
  [8]=>
  string(2) "CC"
}

Dieser Algorithmus bietet einen systematischen Ansatz zur Generierung aller Kombinationen einer bestimmten Größe aus einer bestimmten Menge. Seine rekursive Natur ermöglicht eine effiziente Untersuchung aller möglichen Kombinationen, unabhängig von der Größe des Eingabesatzes.

Das obige ist der detaillierte Inhalt vonWie kann ich mit einem rekursiven Algorithmus alle Kombinationen einer bestimmten Menge in PHP generieren?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!