Comment générer des combinaisons de permutation non répétitive basées sur un jeu de caractères et un nombre de couches, et exclure tous les caractères des mêmes combinaisons?

Génération efficace de disposition et de combinaison de caractères: éviter la duplication et exclure tout de même

Cet article décrit comment générer des combinaisons de permutation non répétitifs basées sur un jeu de caractères donné et un nombre de couches, et exclure efficacement les combinaisons où tous les caractères sont les mêmes. Par exemple, le jeu de caractères est «a» et «b», qui génère une combinaison de couches différentes: la première couche est «a», «b»; La deuxième couche est «ab», «ba» (à l'exclusion «aa», «bb»); La troisième couche contient «Aab», «Aba», «ABB», «baa», «bab», «bba», etc.

Nous adopterons deux stratégies d'algorithme: la méthode de remplacement numérique et la méthode de retournement.

Méthode 1: Méthode de remplacement numérique (plus concise)

Cette méthode traite les permutations comme des nombres à m-chiffre. Prenant le jeu de caractères 'A', 'B' comme exemple, 'A' IS 0 et 'B' IS 1. Combinaison de seconde couche: 00 ('AA'), 01 ('AB'), 10 ('BA'), 11 ('BB'). Itérer à travers tous les nombres de chiffre M et les convertir en combinaisons de caractères. Afin d'exclure la même combinaison, il est déterminé si le nombre de chiffres à m généré peut être divisible par (11 ... 1) (le nombre de 1 est égal au nombre de couches m).

Exemple de code python:

 Def Generate_combinations (charset, couches, allow_all_same = false):
    résultats = []
    n = len (charset)
    all_ones = sum (n ** i pour i dans la plage (couches)))
    pour i dans la gamme (couches n **):
        Si perte_all_same ou i% all_ones! = 0: #Exclude combinaison = ""
            temp = i
            pour _ dans la plage (couches):
                combinaison = combinaison de charset [temp% n]
                temp // = n
            ResultS.APPEND (combinaison)
    Résultats de retour

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']

Méthode 2: Méthode de retour en arrière (plus facile à comprendre)

Backtrace est un algorithme récursif qui essaie toutes les combinaisons. Ajoutez un caractère à la combinaison actuelle à chaque étape et génère récursivement des combinaisons plus longues. Utilisez l'indicateur pour déterminer si la combinaison de courant est le même caractère et évitez la duplication et la même combinaison.

Exemple de code python:

 def generate_combinations_recursive (charse, couches, allow_all_same = false):
    résultats = []
    Current_Combination = [''] * Couches

    Def BackTrack (index, all_same):
        Si index == couches:
            Si pas all_same:
                ResultS.APPEND ("". JOIN (current_combination))
            Retour
        Pour Char in Charset:
            current_combination [index] = char
            BackTrack (Index 1, all_same et char == current_combination [index - 1] si index> 0 else false)

    Pour Char in Charset:
        current_combination [0] = char
        BackTrack (1, pas allow_all_same)

    Résultats de retour


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']

Les deux méthodes peuvent résoudre efficacement le problème et le choix dépend de besoins et de préférences spécifiques. La méthode de remplacement numérique est plus simple et la méthode de retournement est plus facile à comprendre et à développer.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!