Rotirea unui sir

[•XamWaZ]

Am o problema care imi da batai de cam de 3 zile.
Se da un sir de n numere intregi. Sa se toreasca spre stanga cu k pozitii fara a se folosi un sir suplimentar.
exemplu: [1,2,3,4,5,6,7] rotire cu 3 pozitii -> [4,5,6,7,1,2,3].
Si ca indicatie am sa nu fac k rotiri a cate un element deoarece e ineficient.

Am tot incercat sa gasesc un algoritm, insa nu am reusit doar pe cazuri particulare.

[•gabitzish1]

Ca sa rotesti un sir cu K pozitii la stanga poti face asa:

• inversezi pozitiile 1 -> K => K, K-1, ..., 1, K+1, K+2, ..., N
• inversezi pozitiile K+1 -> N => K, K-1, ..., 1, N, N-1 ..., K+1
• inversezi tot sirul => K+1, K+2, ..., N, 1, ..., K

[•klamathix]

Sau poti sa mai concatenezi sirul inca o data la sfarsit
1 2 3 4 5 6 7 1 2 3 4 5 6 7

Acum orice rotatie a sirului initial este o subsecventa de lungime N al acestui sir.

L.E @Gabi Dap, scuze. N-am vazut.

[•gabitzish1]

Se da un sir de n numere intregi. Sa se toreasca spre stanga cu k pozitii fara a se folosi un sir suplimentar.

Concatenand sirul la sfarsit mi se pare ca se foloseste un fel de sir suplimentar

[•SpiderMan]

Poti sa nu faci asta cu concatenarea, faci tot pe sirul V, te duci cu primul for de la K + 1 pana la N, si apoi de la 1 -> K .

[•XamWaZ]

pai e ca si cu un sir suplimentar asa.
@SpiderMan cum zici tu e doar parcurgerea. eu nu vreau sa il parcurg ci sa ii rotesc elementele. la final daca afisez tot sirul sa am elementele rotite.

cum zicea gabitzish1 am gasit si eu o solutie, insa nu prea am inteles cum ziceai acolo.
tot interschimband valorile repetat din k in k pana ajungi de unde ai pornit e cea mai optima solutie.

[•gabitzish1]

Nu stiu cum sa'ti explic mai pe inteles... faci reverse la subsecventa [1 -> K], reverse la subsecventa [K+1 -> N], si reverse la tot sirul apoi (subsecventa [1 -> N]);

[•SpiderMan]

Pai faci ce-o zis Mihai, doar faci cum am zis eu, in loc de pozitia N + 1 .... 2N pui pozitiile din sirul initial , teoretic nu e un sir suplimentar, ca nu-l declari (daca la asta se refera).

[LE] Cum a zis gabitzish1, e foarte bine si asa, ai chiar o functie in STL reverse care face asta lejer .

[•XamWaZ]

@gabitzish1, acum am inteles, cred ca e cel mai simplu asa, la complexitate e la fel ca solutia care am gasit-o ultima data, ca se fac n interschimbari.

@SpiderMan cum zici tu inca raman pe pozitiile 1..k elemente care mie nu imi trebuie si cam sa le sterg trebuie facuti mai multi pasi si deja devine ineficient.

[•laurion]

merge si cu hash-uri

[•wefgef]

merge si cu hash-uri

Nu prea.

[•laurion]

ouch scuze, nu am citit bine, credeam ca trebuie aflat daca un sir e rotirea altuia, asa mergea cu hash-uri... 

[•Fayed]

Poti face permutari circulare la dreapta de k ori.
iata codul:
for(int i=1;i<=k;++i)
{
          aux=V[n];
      for(int j=2;j<=n;++j)   
{     
 V[1]=aux;
V[j]=V[j-1];
  }           
 }

complexitatea este insa de O(n*k)

[•Fayed]

la stanga nu le dreapta. Scuze! Greseala mea.