Nästa större permutation

(26 nov 2020)

Permutation av tre olika färger

Låt oss först förstå vad permutation betyder. Definitionen hämtad från Wikipedia säger ” In matematik , a permutation av en set är löst sagt en ordning av dess medlemmar i en sekvens eller linjär ordning , eller om uppsättningen redan är beställd , en omläggning av dess element. Ordet ”permutation” hänvisar också till handlingen eller processen för att ändra den ordnade uppsättningens linjära ordning.

Så som definitionen säger betyder permutation att ordna om en uppsättning av givna objekt i alla möjliga beställningar. Som vi kan se i ovanstående diagram kan tre olika färger ordnas på sex sätt, dvs. {RGB, RBG, GRB, GBR, BRG, BGR}.

En matematisk formel för att beräkna antalet möjliga arrangemang för n olika objekt ges av n !, där n! = n * (n-1) * (n-2) * … * 1

Det finns många sätt att systematiskt generera alla permutationer i en given sekvens. En klassisk algoritm är baserad på att hitta nästa permutation i lexikografisk / ordbok / alfabetisk ordning, om den existerar.

Så problemet är här, vi får en uppsättning alfabet kanske vi kan kall det en sträng, och vi måste hitta nästa lexikografiska uppsättning alfabet eller nästa lexikografiska större sträng eller strängen som kommer nästa i ordboken efter att den aktuella strängen har samma uppsättning alfabet som i den aktuella strängen.

Låt oss ta ett exempel på siffror för att bättre förstå.

Number = [4,5,2,6,7,3,1]
Nästa större antal blir = [4,5,2, 7,1,3,6 ]

Brute Force

Det första vi kommer att tänka på är att hitta alla permutationer för det angivna numret och det minsta av dessa permutationer som också är större än vårt nuvarande antal kommer att vara vårt svar. Som vi såg ovan finns det n! möjligheter (n = antal siffror i antal), betraktar alla siffror som åtskilda, så om vi fortsätter att hitta alla permutationer för ett visst nummer, tar det O (n!) tid att beräkna. Det är en tung tidskomplexitet om n är ett stort antal.

Optimering

Vi måste tänka på hur vi kan förbättra detta. Om vi ​​observerar noggrant, kanske för en mindre uppsättning siffror, kan vi se ett mönster. Låt oss försöka med några exempel:

[2,1,3] = nästa större antal är 231
[1,1,5] = nästa större antal är 151
[2,3 , 5,4] = nästa större antal är 2435
[3,2,1] = vi kan inte bilda ett tal som är större än det nuvarande antalet från alla möjliga permutationer

Takeaways från ovanstående observation:

Fall 1: [3,2,1]

Här börjar vi flytta från höger ände och försöker hitta det första minskande elementet, så att vi kan ersätta det med element större än sig själv från höger sida av det.

Fall 1: nästa större element är inte möjligt i icke-ökande sekvens

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

index = 1, index för det första minskande elementet från höger ände
hitta nästa större element större än 3 i höger sida av i = 1, byt den med nums [i]
Nu sorterar du de återstående elementen efter i = 1 i stigande ordning för att göra det minsta elementet, vi kan enkelt vända elementen efter i = 1 eftersom de redan är sorterade i den icke-ökande ordningen

Den här grafen visar att vid byte av 4 och 5 är sekvensen som börjar från 8, dvs. 86432 fortfarande sorterad i den icke-ökande ordningen och det är ganska uppenbart eftersom vi ersätter det första minskande elementet med det element som är bara större än det och därmed upprätthålla den icke-ökande ordningen.

En ytterligare observation vi kan ta härifrån är att medan vi söker nästa större element från index j = i + 1 till höger kan vi stoppa sökningen vid index j när num [j] blir mindre än eller lika med num [i], eftersom element efter detta index aldrig kan b e större än siffror [i].

Kodavsnitt

I följande kod, om den näst största permutation är inte möjlig, jag konverterar den till minsta möjliga permutation

Komplexitetsanalys

Time Complexity = O (n) { att hitta det första minskande elementet i värsta fall, t.ex. [1,5,4,3,2]} + O (n) {för att hitta nästa större antal i återstående undermatris till höger} + O (1) {för att byta det första minskande elementet med nästa större element} + O (n / 2) {för att vända undermatrisen från i + 1 till len för att sortera i stigande ordning} = O (n)

Eftersom inget tilläggsutrymme krävs, tar det inget extra utrymme .
Därför rymdkomplexitet: O (1)

Tack för att du ägnar din tid åt den här artikeln. Jag hoppas att du tycker att det är till hjälp och att det ger dig en tydlig inblick.

Om du fortfarande har några frågor är du välkommen att svara. Om du tycker att det är till hjälp kan du dela det med dina kollegor. Dina klappar motiverar mig att skriva fler sådana bloggar! 🙂