Urmează o permutare mai mare

(26 noiembrie 2020)

Permutarea a trei culori diferite

Să înțelegem mai întâi ce înseamnă permutarea. Definiția preluată din Wikipedia spune: „ În matematică , a permutare a set este, liber vorbind, un aranjament al membrilor săi într-o secvență sau ordine liniară sau dacă setul este deja comandat , o rearanjare a elementelor sale. Cuvântul „permutare” se referă și la actul sau procesul de modificare a ordinii liniare a unui set ordonat.

Deci, așa cum se spune în definiție, permutarea înseamnă rearanjarea unui set de obiecte date în toate comenzile posibile. După cum putem vedea în diagrama de mai sus, trei culori diferite pot fi aranjate în 6 moduri, adică {RGB, RBG, GRB, GBR, BRG, BGR}.

O formulă matematică pentru a calcula numărul de aranjamente posibile pentru n obiecte diferite este dat de n !, unde n! = n * (n-1) * (n-2) * … * 1

Există multe modalități de a genera sistematic toate permutările unei secvențe date. Un algoritm clasic se bazează pe găsirea următoarei permutări în ordinea lexicografică / dicționar / alfabetică, dacă există.

Deci, afirmația problemei este că ni se oferă un set de alfabete, poate putem numiți-o șir și trebuie să găsim următorul set lexicografic de alfabete sau următorul șir lexicografic mai mare sau șirul care va apărea în dicționar după șirul curent având același set de alfabete ca în șirul curent.

Să luăm un exemplu de numere pentru a înțelege mai bine.

Număr = [4,5,2,6,7,3,1]
Următorul număr mai mare va fi = [4,5,2, 7,1,3,6 ]

Forța brută

Primul lucru care ne va veni în minte este să găsim toate permutările numărului dat și cea mai mică dintre aceste permutări care este, de asemenea, mai mare decât numărul nostru actual va fi răspunsul nostru. După cum am văzut mai sus, există n! posibilități (n = numărul de cifre în număr), considerând toate cifrele ca fiind distincte, deci dacă continuăm să găsim toate permutările pentru un număr dat, va dura O (n!) timp pentru a calcula. Este o perioadă dificilă de timp dacă n este un număr mare.

Optimizare

Trebuie să ne gândim cum putem îmbunătăți acest lucru. Dacă observăm cu atenție, poate pentru un set mai mic de numere, am putea vedea un model. Să încercăm cu câteva exemple:

[2,1,3] = următorul număr mai mare este 231
[1,1,5] = următorul număr mai mare este 151
[2,3 , 5,4] = următorul număr mai mare este 2435
[3,2,1] = nu putem forma un număr mai mare decât numărul curent din toate permutările posibile

Takeaways din cele de mai sus observație:

Cazul 1: [3,2,1]

Aici începem să ne deplasăm de la capătul drept și încercăm să găsim primul element descrescător, astfel încât să îl putem înlocui cu element mai mare decât el din partea dreaptă a acestuia.

Cazul 1: următorul element mai mare nu este posibil în secvență care nu crește

Cazul 2: [2,3,5,4]

index = 1, index pentru primul element descrescător de la capătul drept
găsiți următorul element mai mare decât 3 în partea dreaptă a i = 1, schimbați-l cu nums [i]
Acum, sortați elementele rămase după i = 1 în ordine crescătoare pentru a face cel mai mic element, putem inversa elementele după i = 1, deoarece acestea sunt deja sortate în ordinea non-crescătoare

Acest grafic demonstrează că la schimbarea 4 și 5, secvența care începe de la 8, adică 86432 este încă sortată în ordinea ne-crescătoare și este destul de evident deoarece înlocuim primul element descrescător cu elementul care este doar mai mare decât el și, prin urmare, menținerea ordinii fără creștere.

O altă observație pe care o putem lua de aici este, în timp ce căutăm următorul element mai mare din indexul j = i + 1 la dreapta, putem opri căutarea la indexul j când nums [j] devin mai mici sau egale cu nums [i], ca elemente după acel index nu pot niciodată b e mai mare decât nums [i].

Fragment de cod

În următorul cod, în cazul în care următorul cel mai mare permutarea nu este posibilă, o convertesc în cea mai mică permutare posibilă

Analiza complexității

Complexitatea timpului = O (n) { pentru a găsi primul element descrescător în cel mai rău caz, de ex [1,5,4,3,2]} + O (n) {pentru a găsi următorul număr mai mare în sub-matricea rămasă din dreapta} + O (1) {pentru a schimba primul element descrescător cu următorul element mai mare} + O (n / 2) {pentru a inversa sub-matricea de la i + 1 la len pentru a sorta în ordine crescătoare} = O (n)

Deoarece nu este necesar spațiu pentru adăugare, nu va lua spațiu suplimentar .
Prin urmare, Complexitatea spațiului: O (1)

Vă mulțumim că v-ați dedicat timpul acestui articol. Sper că vi se pare de ajutor și vă oferă o perspectivă clară.

Dacă aveți în continuare întrebări, nu ezitați să răspundeți. Dacă vi se pare util, vă rugăm să îl împărtășiți colegilor dvs. Bătăile tale mă motivează să scriu mai multe astfel de bloguri! 🙂