Permutările ies duplicate când lista are elemente care se repetă
Backtracking-ul tratează cele două litere A din „AAB” ca elemente diferite, deci fiecare ordine apare de mai multe ori. Sortează elementele și sari peste un element egal cu cel dinaintea lui la același nivel: if i > 0 and ramase[i] == ramase[i - 1]: continue.
Explicat de Tudor Andrei Dumitrescu, Senior Software Developer, fondatorul Academiei ProgramatorilorActualizat la
Ce înseamnă
Permutările clasice presupun elemente distincte. Pentru 'AAB' există doar 3 ordini diferite (AAB, ABA, BAA), dar algoritmul obișnuit produce 6, pentru că alege o dată primul A și o dată al doilea A pe aceeași poziție, iar rezultatul arată identic.
Nu primești nicio eroare de la Python, doar o listă cu duplicate sau un număr prea mare de rezultate. Același lucru apare la submulțimi și combinații cu elemente care se repetă (meniuri cu ingrediente repetate, colete identice).
Soluția standard: sortezi elementele, ca valorile egale să fie alăturate, și la fiecare nivel al recursivității alegi o singură dată fiecare valoare. set() peste rezultat elimină duplicatele, dar abia după ce le-ai generat pe toate, ceea ce poate fi foarte lent.
De ce apare: cauzele frecvente
1Lipsește saltul peste valori egale pe același nivel
for i in range(len(ramase)):
merg(drum + [ramase[i]], ramase[:i] + ramase[i + 1:])for i in range(len(ramase)):
if i > 0 and ramase[i] == ramase[i - 1]:
continue
merg(drum + [ramase[i]], ramase[:i] + ramase[i + 1:])Dacă valoarea de pe poziția i e aceeași cu cea de pe i - 1, ramura ar produce exact aceleași permutări. continue o sare.
2Elementele nu sunt sortate
merg([], list('ABA'))merg([], sorted('ABA'))Verificarea cu elementul anterior merge doar dacă valorile egale sunt alăturate. Fără sortare, cele două A sunt despărțite de B și duplicatele rămân.
3Elimini duplicatele abia la final
return sorted(set(rezultat))# sari peste valorile egale în timpul generării
return rezultatset() dă rezultatul corect, dar generezi tot de n! ori. La 10 elemente cu multe repetări, diferența e uriașă.
Repară eroarea, direct în pagină
Funcția ordini(colete) trebuie să genereze toate ordinile distincte de livrare. Pentru 'AAB' testul cu assert pică: ies 6 ordini, cu duplicate. Repar-o ca să afișeze 3 și lista ['AAB', 'ABA', 'BAA'].
def ordini(colete):
rezultat = []
def merg(drum, ramase):
if not ramase:
rezultat.append(''.join(drum))
return
for i in range(len(ramase)):
merg(drum + [ramase[i]], ramase[:i] + ramase[i + 1:])
merg([], sorted(colete))
return rezultat
rez = ordini('AAB')
assert rez == ['AAB', 'ABA', 'BAA'], f'ordini duplicate: {rez}'
print(len(rez))
print(rez)3 ['AAB', 'ABA', 'BAA']
Indiciu
Lista ramase e sortată; în buclă, sari peste un colet egal cu cel de dinaintea lui.
Reparația
def ordini(colete):
rezultat = []
def merg(drum, ramase):
if not ramase:
rezultat.append(''.join(drum))
return
for i in range(len(ramase)):
if i > 0 and ramase[i] == ramase[i - 1]:
continue
merg(drum + [ramase[i]], ramase[:i] + ramase[i + 1:])
merg([], sorted(colete))
return rezultat
rez = ordini('AAB')
assert rez == ['AAB', 'ABA', 'BAA'], f'ordini duplicate: {rez}'
print(len(rez))
print(rez)De ce merge
Pe fiecare nivel, codul alegea o dată primul A și o dată al doilea A, iar cele două ramuri produceau aceleași ordini. Pentru că ramase e sortată (și rămâne sortată după ce scoți un element), valorile egale stau alăturate, deci ramase[i] == ramase[i - 1] recunoaște o valoare deja încercată pe acest nivel. Sărind-o, fiecare ordine apare o singură dată.
Cum o eviți pe viitor
Când enunțul spune „elementele se pot repeta” sau „rezultate distincte”, sortează de la început și adaugă regula de salt peste valori egale. Testează cu un exemplu cu repetări ('AAB', [1, 1, 2]) și verifică numărul de rezultate: pentru 'AAB' trebuie 3, nu 6. itertools.permutations nu elimină duplicatele, deci nu te ajută aici.
Întrebări frecvente
Merge la fel și pentru submulțimi?
Da. La submulțimi, condiția devine if i > start and nums[i] == nums[i - 1]: continue, pentru că nivelul începe de la start, nu de la 0.
De ce nu folosesc direct set(itertools.permutations(...))?
Pentru liste mici e în regulă. Pentru liste mari generezi toate cele n! permutări, inclusiv duplicatele, iar programul devine foarte lent.
Erori înrudite
Backtracking fără drum.pop(): drumul se lungește și lipsesc soluții Ai adăugat elementul în drum înainte de apelul recursiv, dar nu l-ai scos după. Drumul crește la fiecare ramură și nu mai are lungimea cerută. Pune drum.pop() imediat după apelul recursiv, ca să anulezi alegerea înainte de următoarea. Backtracking-ul returnează liste goale: [[], [], []] Ai adăugat în rezultat chiar lista de lucru (rezultat.append(drum)), nu o copie a ei. La final backtracking-ul golește lista, deci toate intrările arată goale. Adaugă o copie: rezultat.append(drum[:]) sau list(drum). RecursionError: maximum recursion depth exceeded Funcția recursivă s-a apelat de prea multe ori fără să se oprească, iar Python a depășit limita de aproximativ 1000 de apeluri imbricate. Adaugă un caz de bază (de exemplu if n <= 1: return 1) și verifică dacă fiecare apel se apropie de el. Învață Algoritmi și structuri de date de la zero, cu exerciții la fiecare lecție
Curs Algoritmi pentru interviuri: lecții scurte, fiecare cu un exercițiu verificat automat, direct în browser. Primele 2 lecții sunt gratuite.
