Seuraava suurempi permutaatio

(26. marraskuuta 2020)

Kolmen eri värin permutaatio

Ymmärretään ensin, mitä permutaatio tarkoittaa. Wikipedian määritelmä kertoo: ” In matematiikka , a permutaatio a set on löyhästi sanottuna jäsentensä järjestely jaksoksi tai lineaarinen järjestys tai jos joukko on jo järjestetty , sen elementtien uudelleenjärjestely. Sana ”permutaatio” viittaa myös järjestettyjen joukkojen lineaarisen järjestyksen muuttamiseen.

Joten, kuten määritelmässä sanotaan, permutaatio tarkoittaa tiettyjen objektijoukkojen uudelleenjärjestämistä kaikki mahdolliset tilaukset. Kuten yllä olevasta kaaviosta voidaan nähdä, kolme eri väriä voidaan järjestää kuudella tavalla, eli {RGB, RBG, GRB, GBR, BRG, BGR}.

Matemaattinen kaava mahdollisten järjestelyjen määrän laskemiseksi n eri objektille on annettu n !, jossa n! = n * (n-1) * (n-2) *… * 1

On monia tapoja luoda järjestelmällisesti tietyn sekvenssin kaikki permutaatiot. Yksi klassinen algoritmi perustuu seuraavan permutaation löytämiseen leksikografisessa / sanakirjassa / aakkosjärjestyksessä, jos sellainen on olemassa.

Joten tässä on ongelma-lause, meille annetaan joukko aakkosia, ehkä voimme kutsumme sitä merkkijonoksi, ja meidän on löydettävä seuraava leksikografinen aakkossarja tai seuraava leksikografinen suurempi merkkijono tai merkkijono, joka tulee seuraavaksi sanakirjassa sen jälkeen, kun nykyisellä merkkijonolla on samat aakkoset kuin nykyisessä merkkijonossa.

Otetaan esimerkki numeroista, jotta ymmärrämme paremmin.

Numero = [4,5,2,6,7,3,1]
Seuraava suurempi luku on = [4,5,2, 7,1,3,6 ]

Raakavoima

Ensimmäinen mieleemme tuleva asia on löytää kaikki annetun numeron permutaatiot ja pienin niistä permutaatioista, joka on myös suurempi kuin nykyinen lukumäärä, on vastauksemme. Kuten näimme yllä, on n! mahdollisuudet (n = lukujen lukumäärä), kun otetaan huomioon kaikki numerot erillisinä, joten jos etsimme kaikkia tietyn luvun permutaatioita, laskemiseen kuluu O (n!) aikaa. Se on raskasta aikaa, jos n on suuri luku.

Optimointi

Meidän on mietittävä, miten voimme parantaa tätä. Jos tarkkailemme tarkkaan, ehkä pienempiä numeroita, saatamme nähdä kuvioita. Yritetään muutamalla esimerkillä:

[2,1,3] = seuraava suurempi luku on 231
[1,1,5] = seuraava suurempi luku on 151
[2,3 , 5,4] = seuraava suurempi luku on 2435
[3,2,1] = emme voi muodostaa nykyistä lukua suurempaa lukua kaikista mahdollisista permutaatioista.

Takeaways from the above havainto:

Tapaus 1: [3,2,1]

Täällä aloitamme liikkumisen oikeasta päästä ja yritämme löytää ensimmäisen laskevan elementin, jotta voimme korvata sen itseään suurempi elementti sen oikealta puolelta.

Tapaus 1: seuraava suurempi elementti ei ole mahdollista ei-kasvavassa järjestyksessä

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

index = 1, oikeanpuoleisen ensimmäisen laskevan elementin hakemisto
etsi seuraava suurempi kuin 3 elementti i = 1: n oikea puoli, vaihda se numeroilla [i]
Lajittele nyt jäljellä olevat elementit i = 1: n jälkeen nousevassa järjestyksessä pienimmän elementin muodostamiseksi, voimme yksinkertaisesti kääntää elementit i = 1: n jälkeen, koska ne on jo lajiteltu kasvavassa järjestyksessä

Tämä kaavio osoittaa, että vaihdettaessa 4 ja 5 sekvenssi, joka alkaa 8: sta, ts. 86432, lajitellaan edelleen ei-kasvavassa järjestyksessä, ja se on aivan selvää, koska korvataan ensimmäinen laskeva elementti juuri sitä suuremmalla ja siten yllä ei-kasvavan järjestyksen ylläpitämistä.

Vielä yksi täältä havaittava havainto on, kun etsimme seuraavaa suurempaa elementtiä indeksistä j = i + 1 oikealle, voimme pysäyttää haun hakemistossa j kun luvuista [j] tulee pienempi tai yhtä suuri kuin luvut [i], indeksin jälkeiset elementit eivät voi koskaan b e suurempi kuin nums [i].

Koodinpätkä

Seuraavassa koodissa, jos seuraavaksi suurin permutaatio ei ole mahdollista, muunnan sen pienimpään mahdolliseen permutaatioon

Kompleksianalyysi

Aikakompleksi = O (n) { löytää ensimmäinen laskeva elementti pahimmassa tapauksessa, esim [1,5,4,3,2]} + O (n) {löytää seuraava suurempi luku jäljellä olevasta alaryhmästä oikealla} + O (1) {vaihtaaksesi ensimmäisen laskevan elementin seuraavaan suurempaan elementtiin} + O. .
Siksi avaruuden monimutkaisuus: O (1)

Kiitos, että käytit aikaa tähän artikkeliin. Toivottavasti pidät siitä hyödyllisenä ja se antaa sinulle selkeän käsityksen.

Jos sinulla on vielä kysyttävää, vastaa rohkeasti. Jos pidät siitä hyödyllisenä, jaa se sitten kollegojesi kesken. Taput kannustavat minua kirjoittamaan lisää tällaisia ​​blogeja! 🙂