Wie generiere ich nicht repetitive Permutationskombinationen basierend auf Charaktersatz und Anzahl der Ebenen und schließen alle Zeichen derselben Kombinationen aus?

Effiziente Erzeugung von Charakteranordnung und Kombination: Vermeiden Sie die Duplikation und schließen Sie dieselbe aus

In diesem Artikel wird beschrieben, wie nicht repetitive Permutationskombinationen auf der Grundlage eines bestimmten Zeichensatzes und der Anzahl der Ebenen erzeugt werden und Kombinationen effektiv ausschließen, bei denen alle Zeichen gleich sind. Zum Beispiel ist der Zeichensatz 'A' und 'B', das eine Kombination verschiedener Schichten erzeugt: Die erste Schicht ist 'A', 'B'; Die zweite Schicht ist 'AB', 'ba' (ohne 'aa', 'bb'); Die dritte Schicht enthält 'Aab', 'Aba', 'Abb', 'Baa', 'Bab', 'BBA' usw.

Wir werden zwei Algorithmus -Strategien anwenden: Methode für digitale Ersatz- und Backtracking -Methode.

Methode 1: Methode für digitale Ersatz (prägnanter)

Diese Methode behandelt Permutationen als M-Digit-Zahlen. Das Annehmen des Charakters 'A', 'B' als Beispiel, 'A' ist 0 und 'B' ist 1. zweiter Schicht Kombination: 00 ('AA'), 01 ('AB'), 10 ('Ba'), 11 ('BB'). Durch alle M-Digit-Zahlen durchlaufen und in Charakterkombinationen umwandeln. Um dieselbe Kombination auszuschließen, wird festgestellt, ob die generierte m-Digit-Zahl durch (11 ... 1) teilbar sein kann (die Anzahl von 1 entspricht der Anzahl der Schichten m).

Beispiel für Python -Code:

 Def generate_combinations (charset, Ebenen, erlauben_all_Same = false):
    Ergebnisse = []
    n = len (charset)
    All_ones = sum (n ** i für i in Bereich (Schichten))
    für i in Reichweite (N ** Schichten):
        Wenn erlaubt_all_Same oder i % All_ones! = 0: #Exclude combination = ""
            temp = i
            für _ im Bereich (Schichten):
                Kombination = charset [temp % n] Kombination
                temp // = n
            results.append (Kombination)
    Rückgabeergebnisse

print (generate_combinations ('ab', 2)) # ['ab', 'ba']
print (generate_combinations ('ab', 2, true)) # ['aa', 'ab', 'ba', 'bb']
print (generate_combinations ('ab', 3)) # ['Aab', 'aba', 'abb', 'baa', 'bab', 'bba']
print (generate_combinations ('abc', 2)) # ['ab', 'ac', 'ba', 'bc', 'ca', 'cb']

Methode 2: Backtracking -Methode (einfacher zu verstehen)

Backtrace ist ein rekursiver Algorithmus, der alle Kombinationen versucht. Fügen Sie der aktuellen Kombination bei jedem Schritt ein Zeichen hinzu und erzeugen rekursiv längere Kombinationen. Verwenden Sie das Flag, um festzustellen, ob die aktuelle Kombination das gleiche Zeichen ist, und vermeiden Sie Duplikation und dieselbe Kombination.

Beispiel für Python -Code:

 Def generate_combinations_recursive (charset, layers, degly_all_Same = false):
    Ergebnisse = []
    current_combination = [''] * Ebenen

    Def Backtrack (Index, All_Same):
        Wenn Index == Schichten:
            Wenn nicht All_Same:
                results.append ("". join (current_combination))
            Zurückkehren
        für char in charset:
            current_combination [index] = char
            Backtrack (Index 1, All_Same und char == current_combination [index - 1] Wenn Index> 0 sonst falsch)

    für char in charset:
        current_combination [0] = char
        Backtrack (1, nicht zulässt_all_Same)

    Rückgabeergebnisse


print (generate_combinations_recursive ('ab', 2)) # ['ab', 'ba']
print (generate_combinations_recursive ('ab', 2, true)) # ['aa', 'ab', 'ba', 'bb']
print (generate_combinations_recursive ('ab', 3)) # ['Aab', 'aba', 'abb', 'baa', 'bab', 'bba']
print (generate_combinations_recursive ('abc', 2)) # ['ab', 'ac', 'ba', 'bc', 'ca', 'cb']

Beide Methoden können das Problem effektiv lösen, und die Auswahl hängt von bestimmten Bedürfnissen und Vorlieben ab. Die digitale Ersatzmethode ist einfacher und die Backtracking -Methode ist einfacher zu verstehen und zu erweitern.

Das obige ist der detaillierte Inhalt vonWie generiere ich nicht repetitive Permutationskombinationen basierend auf Charaktersatz und Anzahl der Ebenen und schließen alle Zeichen derselben Kombinationen aus?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!