Næste større permutation

(26. nov 2020)

Permutation af tre forskellige farver

Lad os først forstå, hvad betyder permutation. Definition taget fra Wikipedia siger, “ I matematik , en permutation af en sæt er løst sagt et arrangement af dets medlemmer i en sekvens eller lineær rækkefølge eller hvis sættet allerede er bestilt , en omlægning af dets elementer. Ordet “permutation” henviser også til handlingen eller processen med at ændre den lineære rækkefølge for et ordnet sæt.

Så som definitionen siger, betyder permutation at omarrangere et sæt af givne objekter i alle mulige ordrer. Som vi kan se i ovenstående diagram, kan tre forskellige farver arrangeres på 6 måder, dvs. {RGB, RBG, GRB, GBR, BRG, BGR}.

En matematisk formel til beregning af antallet af mulige arrangementer for n forskellige objekter er givet af n !, hvor n! = n * (n-1) * (n-2) * … * 1

Der er mange måder at systematisk generere alle permutationer af en given sekvens. En klassisk algoritme er baseret på at finde den næste permutation i leksikografisk / ordbog / alfabetisk rækkefølge, hvis den findes.

Så problemstillingen her er, vi får et sæt alfabeter måske kan vi kalder det en streng, og vi er nødt til at finde det næste leksikografiske sæt alfabeter eller næste leksikografisk større streng eller den streng, der kommer næste i ordbogen efter den aktuelle streng, der har det samme sæt alfabeter som i den aktuelle streng.

Lad os tage et eksempel på tal for at forstå det bedre.

Number = [4,5,2,6,7,3,1]
Næste større antal bliver = [4,5,2, 7,1,3,6 ]

Brute Force

Den første ting, som vi kommer til at tænke på, er at finde alle permutationer af det givne antal og den mindste af disse permutationer, som også er større end vores nuværende antal, vil være vores svar. Som vi så ovenfor, er der n! muligheder (n = antal cifre i antal), betragter alle cifrene som forskellige, så hvis vi fortsætter med at finde alle permutationer for et givet tal, vil det tage O (n!) tid at beregne. Det er en tung tidskompleksitet, hvis n er et stort antal.

Optimering

Vi er nødt til at tænke over, hvordan vi kan forbedre dette. Hvis vi observerer nøje, måske for et mindre sæt tal, kan vi muligvis se mønstre. Lad os prøve med et par eksempler:

[2,1,3] = næste større antal er 231
[1,1,5] = næste større antal er 151
[2,3 , 5,4] = næste større antal er 2435
[3,2,1] = vi kan ikke danne et tal større end det aktuelle antal ud fra alle mulige permutationer

Takeaways fra ovenstående observation:

Sag 1: [3,2,1]

Her begynder vi at bevæge os fra højre ende og forsøger at finde det første faldende element, så vi kan erstatte det med element større end sig selv fra højre side af det.

Tilfælde 1: næste større element er ikke mulig i ikke-stigende rækkefølge

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

index = 1, indeks for det første faldende element fra højre ende
find det næste større element større end 3 i højre side af i = 1, skift det med nums [i]
Nu skal du sortere de resterende elementer efter i = 1 i stigende rækkefølge for at gøre det mindste element, vi kan simpelt vende elementerne efter i = 1, da de allerede er sorteret i ikke-stigende rækkefølge

Denne graf beviser, at ved at bytte 4 og 5 er sekvensen startende fra 8, dvs. 86432 stadig sorteret i ikke-stigende rækkefølge, og det er ret indlysende, da vi erstatter det første faldende element med det element, der bare er større end det og dermed opretholde den ikke-stigende rækkefølge.

En yderligere observation, vi kan tage herfra, er, mens vi søger efter det næste større element fra indeks j = i + 1 til højre, kan vi stoppe søgningen ved indeks j når nums [j] bliver mindre end eller lig med nums [i], da elementer efter dette indeks aldrig kan b e større end numre [i].

Kodestykke

I den følgende kode, hvis den næststørste permutation er ikke mulig, jeg konverterer den til den mindst mulige permutation

Kompleksitetsanalyse

Time Complexity = O (n) { at finde det første faldende element i værste fald, f.eks [1,5,4,3,2]} + O (n) {for at finde det næste større antal i det resterende underarray til højre} + O (1) {for at bytte det første faldende element med det næste større element} + O (n / 2) {for at vende underarrayet fra i + 1 til len for at sortere i stigende rækkefølge} = O (n)

Da der ikke kræves noget ekstra plads, tager det ikke ekstra plads .
Derfor Rumkompleksitet: O (1)

Tak, fordi du afsætter din tid til denne artikel. Jeg håber, du finder det nyttigt, og det giver dig et klart indblik.

Hvis du stadig har spørgsmål, er du velkommen til at svare. Hvis du finder det nyttigt, så del det med dine kolleger. Dine klapper motiverer mig til at skrive flere sådanne blogs! 🙂