Generare in ordine lexicografica

Dau bacul la informatica si din toate problemele singurele pe care nu le-am inteles sunt cele cu backtracking.
Nu inteleg in ce ordine sunt generate elementele.
O sa va arat un tip de problema.

"Se utilizeaza metoda backtracking pentru a se genera in ordine lexicografica toate cuvintele care contin toate literele din multimea {a,m,i,c}, astfel incat sa apara exact o data intr-un cuvant. Cate solutii sunt generate dupa cuvantul amic si inainte de cuvantul cami?"

Daca cineva imi poate oferi o explicatie sau macar o insiruire a elementelor generate as fi recunoscator.

Backtrackingul genereaza multimi care se afla in oridine crescatoare(lexiografic) astfel
1234 1243, 1324, 1342, 1423, 1432, 2134, 2143 etc. pana la 4321. La tine 1=a, 2=m, 3=i, 4=c. Daca dai bacu la info si nu stii inca asta e destul de grav... :D.

 korn3l, on 6th June 2009, 19:42, said:

ce mai buna explicatie este: ia o foaie ,un  creionul  si spor la generarea solutiilor ;)
Plus asta trebuia sa sti din a 10 cand ai facut probleme de numarare ... combinatii, aranjamente, permutari..etc

Stii diferenta dintre un limbaj de programare si un algoritm? Cand o sa o afli te astept sa postezi la C++, pana atunci expediez topicul putin mai sus.

 andrei31, on 6th June 2009, 19:50, said:

Aparent se pare ca nici tu nu stii. Generarea normala se face asa cum ai zis tu, asta stiam si eu. Chestia e ca atunci cand sunt generate in ordine lexicografica se renunta la unele dintre ele si nu stiu exact care si mai ales in ce ordine vor fi generate.

Problema are raspunsurile: a.6 b.4 c.1 d.3
Deci e clar ca nu e asa cum ai zis tu.

Edited by korn3l, 07 June 2009 - 13:04.

ba e asa cum a spus el. problema te intreaba cate cuvinte sunt intre 2 limite, de aia ai raspunsurile alea. deci pe linga faptul ca le generezi, trebuie sa numeri cuvintele intre 2 limite, amic si cami. tu ai zis ca ai probleme cu generarea nu cu numararea, deci ai primit explicatii in acel sens. daca in prag de bac nci sa numeri cate elemente sunt intre cele doua limite nu stii ...
daca te ajuta mai mult, ceea ce trebuie sa faci este defapt adunare in baza 4 pe elemente de 4 cifre cu ignorarea/filtrarea celor care nu respecta conditia de unicitate a cifrelor. cel mai optim este ca pornesti de la amic si adaugi "1" pina ajungi la cami si ai rezolvat problema frumos si elegant. dar comisia de la bac s-ar putea sa priveasca lucrurile cu alti ochi, deci daca vrei sa nu te dai in barci cu reexaminari si vrei neaparat (si ai timp) ofera atat solutia eleganta cat si cea asteptata de ei (adica backtrackingul clasic)

Edited by ciuly, 07 June 2009 - 13:15.

din cate exercitii d backtracking am facut si luandu'ma si dupa raspunsuri am observat k ordinea lexicografica se refera la ordinea alfabetica...deci spre exemplu dak avem literele {a,m,i,c}  notam ca sa ne fie mai usor fiecare litera cu cate o cifra IN ORDINE ALFABETICA deci avem a=1 c=2 i=3 m=4 dupa care generam solutiile dupa metoda generala.incearca asa si vezi dak iasa cum trebuie.sper k te'am putut ajuta si nu am raspuns prea tarziu  :rolleyes:  bafta!

 andrei31, on 06 iunie 2009 - 18:50, said:

Nu e asa. Daca multimea e {a,m,i,c} prima solutie generata va fi "acim" nu spune ordine lexicografica a indicilor ca sa mergi pe ideea cu 1234, se merge in functie de ordinea alfabetica. Sper ca am lamurit