Volgende grotere permutatie

(26 nov.2020)

Permutatie van drie verschillende kleuren

Laten we eerst begrijpen wat permutatie betekent. De definitie uit Wikipedia zegt: “ In wiskunde , een permutatie van een set is, losjes gezegd, een rangschikking van de leden in een reeks of lineaire volgorde , of als de set al is besteld , een herschikking van de elementen. Het woord “permutatie” verwijst ook naar de handeling of het proces van het veranderen van de lineaire volgorde van een geordende set.

Dus, zoals de definitie zegt, betekent permutatie het herschikken van een set van gegeven objecten in alle mogelijke bestellingen. Zoals we in het bovenstaande diagram kunnen zien, kunnen drie verschillende kleuren op 6 manieren worden gerangschikt, namelijk {RGB, RBG, GRB, GBR, BRG, BGR}.

Een wiskundige formule om het aantal mogelijke arrangementen te berekenen voor n verschillende objecten wordt gegeven door n !, waarbij n! = n * (n-1) * (n-2) *… * 1

Er zijn veel manieren om systematisch alle permutaties van een gegeven reeks te genereren. Een klassiek algoritme is gebaseerd op het vinden van de volgende permutatie in lexicografische / woordenboek / alfabetische volgorde, als die bestaat.

Dus, de probleemstelling hier is dat we een reeks alfabetten krijgen, misschien kunnen we dat noem het een string, en we moeten de volgende lexicografische set alfabetten of de volgende lexicografische grotere string vinden of de string die als volgende in het woordenboek komt na de huidige string met dezelfde set alfabetten als in de huidige string.

Laten we een voorbeeld nemen van getallen om ze beter te begrijpen.

Getal = [4,5,2,6,7,3,1]
Het volgende grotere getal is = [4,5,2, 7,1,3,6 ]

Brute kracht

Het eerste dat in ons opkomt is: vind alle permutaties van het gegeven aantal en de kleinste van die permutaties die ook groter is dan ons huidige aantal zal ons antwoord zijn. Zoals we hierboven hebben gezien, zijn er n! mogelijkheden (n = aantal cijfers in getal), waarbij alle cijfers als verschillend worden beschouwd, dus als we alle permutaties voor een bepaald getal blijven vinden, zal het O (n!) tijd kosten om te berekenen. Dat is een grote tijdscomplexiteit als de n een groot getal is.

Optimalisatie

We moeten nadenken hoe we dit kunnen verbeteren. Als we zorgvuldig observeren, misschien voor een kleinere reeks getallen, kunnen we patronen zien. Laten we een paar voorbeelden proberen:

[2,1,3] = het volgende hogere getal is 231
[1,1,5] = het volgende hogere getal is 151
[2,3 , 5,4] = het volgende grotere getal is 2435
[3,2,1] = we kunnen geen getal vormen dat groter is dan het huidige getal uit alle mogelijke permutaties

Afhaalrestaurants van het bovenstaande observatie:

Geval 1: [3,2,1]

Hier beginnen we te bewegen vanaf de rechterkant en proberen we het eerste afnemende element te vinden, zodat we het kunnen vervangen door de element groter dan zichzelf vanaf de rechterkant ervan.

Geval 1: het volgende grotere element is niet mogelijk in niet-oplopende volgorde

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

index = 1, index voor het eerste afnemende element vanaf de rechterkant
vind het volgende grotere element groter dan 3 in de rechterkant van i = 1, verwissel het met nums [i]
Sorteer nu de resterende elementen na i = 1 in oplopende volgorde om het kleinste element te maken, we kunnen de elementen na i = 1 eenvoudig omkeren, aangezien ze al in niet-oplopende volgorde zijn gesorteerd

Deze grafiek bewijst dat bij het verwisselen van 4 en 5, de reeks die begint bij 8, dwz 86432 nog steeds wordt gesorteerd in de niet-oplopende volgorde en het is vrij duidelijk omdat we het eerste afnemende element vervangen door het element dat gewoon groter is dan het en dus het handhaven van de niet-oplopende volgorde.

Nog een observatie die we vanaf hier kunnen nemen, is dat we tijdens het zoeken naar het volgende grotere element van index j = i + 1 naar rechts het zoeken kunnen stoppen bij index j wanneer nums [j] kleiner worden dan of gelijk aan nums [i], zoals elementen na die index nooit b e groter dan nums [i].

Codefragment

In de volgende code, voor het geval de volgende permutatie is niet mogelijk, ik zet het om in de kleinst mogelijke permutatie

Complexiteitsanalyse

Tijdscomplexiteit = O (n) { om in het ergste geval het eerste afnemende element te vinden, bijv [1,5,4,3,2]} + O (n) {om het volgende grotere getal in de resterende subarray aan de rechterkant te vinden} + O (1) {om het eerste afnemende element te verwisselen met het volgende grotere element} + O (n / 2) {om de subarray om te keren van i + 1 naar len om in oplopende volgorde te sorteren} = O (n)

Aangezien er geen extra ruimte nodig is, neemt het geen extra ruimte in beslag .
Vandaar de complexiteit van de ruimte: O (1)

Bedankt dat u uw tijd aan dit artikel besteedt. Ik hoop dat je het nuttig vindt en dat het je een duidelijk inzicht geeft.

Als je nog vragen hebt, reageer dan gerust. Als u het nuttig vindt, deel het dan met uw collegas. Je klappen motiveren me om meer van dergelijke blogs te schrijven! 🙂