infoarena

Aici puteţi discuta despre problema Generare de permutari (http://infoarena.ro/problema/permutari).

O idee alternativa este generarea iterativa.
 O scurta descriere :
Fie p[1],p[2],...p[n] o permutare data.
1. Se cauta din coada prima pozitie de crestere adica adica
p[ i ]<p[ i+1 ] ( 1<= i  < n ) i=maxim
2. Se cauta din coada prima pozitie j pentru care in care p[ j ] > p[ i ] .
3. Se schimba intre ele elementele din pozitiile i si j .
4. Se reverseaza secventa  i+1 -> n.
Astfel se genereaza permutarea urmatoare in ordine lexicografica

Ceva asemanator face si next_permutation in STL. Cred ca ar trebuie mentionata si solutia asta in indicatii. O alta posibilitate mai e sa iei fiecare numar de la 1 la N! si sa determine ce permutare reprezinta.

Dap. Scazand factoriale in ordine descrescatoare.

Trebuia mentionata si solutia cu dancing links.

Cred ca cel mai bine cand vine cineva cu o solutie noua e sa adauge el la indicatii de rezolvare, asa e greu sa te gandesti din prima la toate solutiile :roll:. Adica problemele pot fi modificate si pe parcurs, dupa ce ies la rampa. In plus, daca mai stiti probleme similare care folosesc algoritmii prezentati, completati ca sa obtinem o lista cat mai buna.

Nu trebuie sa fii decat admin :P Se poate face o noua pagina /problema/nume/indicatii care sa fie editabila de oricine si inclusa in problema.

Am postat solutia folosind si backtracking, si generarea permutarii urmatoare, dar totusi imi iese din timp la ultimul test. de ce? :fool:

@vlad_oltean
Fa scrierea si citirea in C, si scrie functia afis()  inline.

multumesc pentru sfat, am modificat si am luat si eu suta :thumbup: dar oricum, de ce stdio merge mai repede decat fstream??  :-s

sorry mods, nu e chiar ontopic
@vlad_oltean
Actualy nu e stdin si fstream :P astea sunt headere, care contin definitiile functiilor de citire.

Nu intodeuna citirile in C sunt mai rapide decat cele in C++.
Toate depind de implementarea lor data de compilator. Depinde de ce flaguri de compilare folosesti,
depinde de ce optimizari mai ai in cod etc..
Sa nu repet familia de functii de citire in C si C++, am sa ma refer la scanf si cin.
Nu poti zice cu siguranta ca "scanf" e mai rapida decat "cin" sa zicem.
Oricum in cazul asta si in majoritatea cazurilor unde folosesti direct functiile, diferenta de viteza e in fravoarea scanf clar.
Provine de la faptul ca cin e un obiect de tip istream, care trebuie construit, distrus, manipulat, e mare.. in fine.. e un obiect si se misca mai greu (object overhead). Bineinteles cum se misca de optimizarile compilatorului. "scanf" nu foloseste obiecte ci e o functie caruia ii dai un pattern de citire si niste pointeri, acesul in memorie se face mai rapid in cazul asta.
Niste linkuri pe tema asta:

http://forums.topcoder.com/?module=Thread&threadID=508058&start=0&mc=7
http://www.cplusplus.com/reference/iostream/
Ah si discutia prea funny in care brahle e cam owned pe subiectul asta :)
http://www.daniweb.com/forums/thread40450.html

Ar merge un articol in care se discuta chestiile astea.

Am facut problema cu next_permutation din STL. Cu streamuri (pe calcul meu) compilatorul MinGW spunea ca executia a durat 0.5 secunde, cu stdio doar 0.2 secunde.

Cu ifstream si ofstream (68ms testul 5 pentru N=8) merge mai repede decat cu freopen (80ms testul 5 pentru N=8)

WOOW !  :shock: Pe bune ?!?

Ce complexitate are functia  next_permutation? O(1)?

http://www.cplusplus.com/reference/algorithm/next_permutation/

"Up to linear in half the distance between first and last (in terms of actual swaps)." (http://www.cplusplus.com/reference/algorithm/next_permutation/ (http://www.cplusplus.com/reference/algorithm/next_permutation/))

Deci O(N/2), care poate fi aproximat la O(1) (pentru N <=8).

https://infoarena.ro/job_detail/2202619?action=view-source

80 puncte, fail pe ultimul test.
Any ideas?  :)