...
Eroare Algoritmi și structuri de date · Recursivitate și backtracking

Permutările ies duplicate când lista are elemente care se repetă

Pe scurt

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

Greșit
PYTHON
for i in range(len(ramase)):
    merg(drum + [ramase[i]], ramase[:i] + ramase[i + 1:])
Corect
PYTHON
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

Greșit
PYTHON
merg([], list('ABA'))
Corect
PYTHON
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

Greșit
PYTHON
return sorted(set(rezultat))
Corect
PYTHON
# sari peste valorile egale în timpul generării
return rezultat

set() dă rezultatul corect, dar generezi tot de n! ori. La 10 elemente cu multe repetări, diferența e uriașă.

Repară tu

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

Codul care dă eroarea
PYTHON
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)
După reparație, programul afișează
3
['AAB', 'ABA', 'BAA']
Indiciu

Lista ramase e sortată; în buclă, sari peste un colet egal cu cel de dinaintea lui.

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

← Toate erorile Algoritmi și structuri de date

Tudor Andrei Dumitrescu
Cine a explicat eroarea

Tudor Andrei Dumitrescu

Senior Software Developer · fondatorul Academiei Programatorilor

LinkedIn
  1. 2019 Junior JavaCognizant Softvision
  2. 2021 Mid JavaCognizant Softvision
  3. 2022 Team LeaderEndava
  4. 2023 Senior Software DeveloperUniCredit
  5. Acum Senior Software DeveloperHCLTech
Certificat de absolvire Instructor / Preparator formare, Tudor Andrei Dumitrescu
Certificat de formator autorizatMinisterul Muncii și Ministerul Educației · 2022
Certificat de absolvire Instructor / Preparator formare, Tudor Andrei Dumitrescu

Certificat de formator autorizat · Ministerul Muncii și Ministerul Educației · 2022

Din 2020 construiește Academia Programatorilor, iar din 2026 și JoburiIT.ro. Fiecare eroare de aici a fost reprodusă în editorul nostru: codul greșit chiar dă mesajul din titlu, iar reparația chiar funcționează.

Î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.