Wie kann ich mithilfe eines rekursiven Ansatzes alle möglichen Kombinationen einer bestimmten Größe aus einem bestimmten Zeichensatz generieren?

Algorithmus zum Generieren von Kombinationen aus einem einzelnen Satz

Die vorliegende Aufgabe besteht darin, einen Algorithmus zu entwickeln, der alle möglichen Kombinationen eines bestimmten Satzes generieren kann Größe aus einem bestimmten Zeichensatz und fungiert effektiv als Sampling-Algorithmus. Im Gegensatz zu Permutationsalgorithmen ermöglicht diese Technik die Wiederholung von Zeichen innerhalb von Kombinationen.

Rekursiver Ansatz

Um dieses Problem anzugehen, verwenden wir eine rekursive Funktion, die als Eingabe das verwendet Zeichensatz, die gewünschte Kombinationsgröße und ein Array von Zwischenkombinationen (initialisiert als Originalsatz für die Initiale). Iteration).

1. Basisfall: Wenn die Größe 1 ist, gibt die Funktion den aktuellen Satz von Kombinationen zurück.

2. Rekursiver Schritt :

   • Erstellen Sie ein leeres Array für den neuen Satz von Kombinationen.
   • Verketten Sie alle vorhandenen Kombinationen und Zeichen im Satz und hängen Sie sie an das neue Array an.
   • Erinnern Sie sich an dieselbe Funktion mit dem aktualisierten Zeichensatz (unverändert), reduzierter Größe, und neue Kombinationen als Eingabe.

Beispiel Implementierung

Der folgende PHP-Code veranschaulicht die Implementierung des rekursiven Algorithmus:

function sampling($chars, $size, $combinations = array()) {

    // Base case
    if (empty($combinations)) {
        $combinations = $chars;
    }

    // Size 1 case
    if ($size == 1) {
        return $combinations;
    }

    // Initialize new combinations array
    $new_combinations = array();

    // Generate new combinations by concatenating existing and new characters
    foreach ($combinations as $combination) {
        foreach ($chars as $char) {
            $new_combinations[] = $combination . $char;
        }
    }

    // Recursive call
    return sampling($chars, $size - 1, $new_combinations);

}

Beispielverwendung

Um die Funktionalität zu demonstrieren, Betrachten wir eine Reihe von Zeichen:

$chars = array('a', 'b', 'c');

Mit dem Algorithmus können wir alle Kombinationen generieren der Größe 2:

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

Das obige ist der detaillierte Inhalt vonWie kann ich mithilfe eines rekursiven Ansatzes alle möglichen Kombinationen einer bestimmten Größe aus einem bestimmten Zeichensatz generieren?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!