Je suis un débutant essayant d'apprendre la récursion en Python. Je veux imprimer toutes les permutations d'une chaîne donnée. Par exemple:
Entrée : AABC
Sortie : AABC, AACB, ABAC, ABCA, ACAB, BAAC, BACA, BCAA, CAAB, CABA, CBAA
J'ai écrit le code suivant en Python en utilisant la récursivité.
def foo(str,count):
result = ""
while(any(count)):
for i in range(len(count)):
if count[i]>0:
count[i] -= 1
result = str[i] + foo(str,count)
print(result)
return result
s = "AABC"
n = 4
c = {}
for i in range(len(s)):
if s[i] in c:
c[s[i]] += 1
else:
c[s[i]] = 1
str = list(c.keys())
count = list(c.values())
print(str,count)
foo(str,count)
print(count)
Je reçois le résultat comme suit:
['A', 'B', 'C'] [2, 1, 1]
C
BC
ABC
AABC
[0, 0, 0]
Cela implique que le code ne gère que le premier cas à chaque niveau. Comment puis-je corriger ce code?
Toute aide serait merveilleuse.
Merci pour votre temps :)
3 Réponses :
Je ne sais pas pourquoi vous utilisez count mais voici une façon de le faire de manière récursive (pas très optimale cependant). :
AABC AACB ABAC ABCA ACAB ACBA AABC AACB ABAC ABCA ACAB ACBA BAAC BACA BAAC BACA BCAA BCAA CAAB CABA CAAB CABA CBAA CBAA
Sortie:
def foo(s,result):
if len(result) == 4:
print(result)
if len(s) == 0:
return
for i in range(len(s)):
new_s = s.copy()
del new_s[i]
foo(new_s,result + s[i])
s = list('AABC')
foo(s,'')
Si vous voulez des chaînes distinctes, vous pouvez les ajouter à un ensemble
Votre code semble un peu brouillon et j'ai du mal à comprendre comment vous avez essayé de résoudre votre problème avec celui-ci. J'ai essayé de créer une solution aussi simple que possible pour vous aider à comprendre la logique derrière la création de combinaisons de tout type de liste.
def combinations(x):
if len(x) == 1:
yield x
for idx, i in enumerate(x):
for comb in combinations(x[:idx]+x[idx+1:]):
yield i + comb
s = "AABC"
print(list(combinations(s))) # -> ['AABC', 'AACB', 'ABAC', 'ABCA', 'ACAB' ...
x [: idx] + x [idx + 1:] ici est juste court de se débarrasser de l'élément de x à la position de idx . Ajoutez un commentaire si vous avez des questions afin que je puisse vous aider à mieux comprendre ma solution.
Merci cela fonctionne. Mais je suis inconnu avec énumérable.
Si vous connaissez zip () , voici comment cela pourrait être implémenté zip (range (len (list)), list) . Également enumerate () documents
J'ai trouvé quelque chose qui fonctionne mais qui donne des réponses en double à cause de multiples occurrences du caractère 'A', donc j'ai utilisé set () pour obtenir la réponse désirée.
def foo(s,l,result):
if len(result)==4:
l.append(result)
for i in range(len(s)):
foo(s[0:i]+s[i+1:],l,result+s[i])
s = "AABC"
l = []
r = foo(s,l,"")
print(list(set(l)))
Est-ce que cela répond à votre question? Permutations de récursivité Python
À quoi sert
count?Count sert à stocker le nombre d'occurrences de chaque caractère dans une chaîne.