Comment générer une combinaison de permutation qui ne se répète pas et ne fait pas de caractères identiques contigus basés sur un jeu de caractères donné et un nombre de couches?

Ensembles de caractères et couches: générer efficacement des permutations uniques

Cet article explore comment générer une combinaison de permutation sans doublons et sans caractères identiques consécutifs basés sur un jeu de caractères donné et un nombre de couches. Par exemple, le jeu de caractères {a, b}, la combinaison de permutation à trois couches doit contenir AAB, ABA, ABB, BAA, BAB, BBA, etc., mais pas AAA, BBB et d'autres caractères répétés consécutifs. Cela nécessite des algorithmes pour gérer la déduplication et éviter la duplication continue des caractères.

Le défi de base consiste à concevoir un algorithme qui peut s'adapter à différents jeux de caractères et couches et générer efficacement des permutations qui répondent aux critères. Cet article introduira deux méthodes: la méthode de remplacement numérique et la méthode de retournement.

Méthode 1: Méthode de remplacement numérique

Cette méthode traite la combinaison de permutation comme un numéro de chiffre M (m est la taille du jeu de caractères). Par exemple, le jeu de caractères {a, b} correspond à un numéro binaire. 00 représente AA, 01 représente AB, etc. En parcourant tous les numéros de chiffre M et en remplaçant les caractères, vous pouvez obtenir toutes les combinaisons possibles. Pour éviter des caractères identiques continus, des nombres spécifiques à M-chiffres doivent être exclus, comme les nombres où tous les bits sont les mêmes.

Exemple de code python:

 def Solve_Digit (arr, m, allow_all_same = false):
    res, cur = [], [''] * m
    n = len (arr)
    all_same_num = 0
    pour _ dans la gamme (m):
        all_same_num = all_same_num * n 1
    pour d dans la gamme (n ** m):
        Si perte_all_same ou d% all_same_num! = 0:
            pour I à portée (M - 1, -1, -1):
                cur [i] = arr [d% n]
                d // = n
            res.append (''. join (cur))
    Retour Res

print (solve_digit ('ab', 2)) # ['ab', 'ba']
print (solve_digit ('ab', 2, true)) # ['aa', 'ab', 'ba', 'bb']
print (solve_digit ('ab', 3)) # ['aab', 'aba', 'abb', 'baa', 'bab', 'bba']
print (solve_digit ('ABC', 2)) # ['AB', 'AC', 'BA', 'BC', 'CA', 'CB']

Méthode 2: méthode de retour en arrière

Backtrace est un algorithme récursif qui trouve des résultats en essayant toutes les combinaisons possibles. Ajoutez un caractère à la combinaison actuelle à chaque étape et génère récursivement des combinaisons plus longues. Dans le même temps, il est nécessaire de expliquer si les caractères précédents sont les mêmes pour éviter les combinaisons qui ne remplissent pas les conditions.

Exemple de code python:

 def Solve_BackTracking (arr, m, allow_all_same = false):
    res, cur = [], [''] * m

    def dfs (i, même):
        Si i == m:
            Si ce n'est pas le même:
                res.append (''. join (cur))
            Retour
        pour A dans Arr:
            cur [i] = a
            dfs (i 1, même et a == cur [i - 1])

    pour A dans Arr:
        Cur [0] = A
        DFS (1, pas allow_all_same)

    Retour Res

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

Les deux méthodes peuvent résoudre le problème. La méthode de remplacement numérique est plus efficace et la méthode de retour en arrière est plus facile à comprendre. La méthode à choisir dépend du scénario d'application spécifique et des préférences personnelles.

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!