Prossima permutazione maggiore

(26 novembre 2020)

Permutazione di tre diversi colori

Per prima cosa capiamo cosa significa permutazione. La definizione tratta da Wikipedia dice: “ In matematica , un permutazione di set è, in parole povere, una disposizione dei suoi membri in una sequenza o ordine lineare o se il set è già ordinato , una riorganizzazione dei suoi elementi. La parola “permutazione” si riferisce anche allatto o al processo di cambiare lordine lineare di un insieme ordinato.

Quindi, come dice la definizione, permutazione significa riorganizzare un insieme di oggetti dati in tutti gli ordini possibili. Come possiamo vedere nel diagramma sopra, tre diversi colori possono essere disposti in 6 modi, ovvero {RGB, RBG, GRB, GBR, BRG, BGR}.

Una formula matematica per calcolare il numero di arrangiamenti possibili per n oggetti diversi è dato da n !, dove n! = n * (n-1) * (n-2) *… * 1

Ci sono molti modi per generare sistematicamente tutte le permutazioni di una data sequenza. Un algoritmo classico si basa sulla ricerca della successiva permutazione in ordine lessicografico / dizionario / alfabetico, se esiste.

Quindi, laffermazione del problema qui è che ci viene dato un insieme di alfabeti forse possiamo chiamiamola stringa, e dobbiamo trovare il prossimo insieme lessicografico di alfabeti o la prossima stringa lessicografica più grande o la stringa che verrà nel dizionario dopo la stringa corrente che ha lo stesso insieme di alfabeti della stringa corrente.

Facciamo un esempio di numeri per capire meglio.

Numero = [4,5,2,6,7,3,1]
Il prossimo numero maggiore sarà = [4,5,2, 7,1,3,6 ]

Forza bruta

La prima cosa che ci verrà in mente è trovare tutte le permutazioni del numero dato e la più piccola di quelle permutazioni che è anche maggiore del nostro numero attuale sarà la nostra risposta. Come abbiamo visto sopra, ci sono n! possibilità (n = numero di cifre in numero), considerando tutte le cifre come distinte, quindi se continuiamo a trovare tutte le permutazioni per un dato numero, ci vorrà O (n!) tempo per calcolare. Questa è una complessità temporale pesante se n è un numero elevato.

Ottimizzazione

Dobbiamo pensare a come possiamo migliorare questo aspetto. Se osserviamo attentamente, forse per un insieme più piccolo di numeri, potremmo vedere uno schema. Proviamo con alcuni esempi:

[2,1,3] = il numero maggiore successivo è 231
[1,1,5] = il numero maggiore successivo è 151
[2,3 , 5,4] = il numero successivo maggiore è 2435
[3,2,1] = non possiamo formare un numero maggiore del numero attuale da tutte le possibili permutazioni

Conclusioni da quanto sopra osservazione:

Caso 1: [3,2,1]

Qui iniziamo a spostarci dallestremità destra e proviamo a trovare il primo elemento decrescente, in modo da poterlo sostituire con il elemento maggiore di se stesso dal lato destro di esso.

Caso 1: lelemento successivo maggiore non è possibile in sequenza non crescente

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

index = 1, indice per il primo elemento decrescente dallestremità destra
trova lelemento successivo più grande maggiore di 3 nella lato destro di i = 1, scambialo con nums [i]
Ora, ordina gli elementi rimanenti dopo i = 1 in ordine crescente per creare lelemento più piccolo, possiamo semplicemente invertire gli elementi dopo i = 1 poiché sono già ordinati in ordine non crescente

Questo grafico dimostra che scambiando 4 e 5, la sequenza a partire da 8, cioè 86432 è ancora ordinata in ordine non crescente ed è abbastanza ovvio poiché stiamo sostituendo il primo elemento decrescente con lelemento che è appena più grande di esso e quindi mantenendo lordine non crescente.

Unaltra osservazione che possiamo trarre da qui è che mentre si cerca lelemento successivo più grande dallindice j = i + 1 a destra, possiamo fermare la ricerca allindice j quando nums [j] diventa minore o uguale a nums [i], poiché gli elementi dopo quellindice non possono mai b e maggiore di nums [i].

Snippet di codice

Nel codice seguente, nel caso in cui il successivo più grande la permutazione non è possibile, la sto convertendo nella più piccola permutazione possibile

Analisi della complessità

Complessità temporale = O (n) { per trovare il primo elemento decrescente nel caso peggiore, ad es [1,5,4,3,2]} + O (n) {per trovare il numero successivo maggiore nel restante sotto-array a destra} + O (1) {per scambiare il primo elemento decrescente con lelemento successivo più grande} + O (n / 2) {per invertire larray secondario da i + 1 a len per ordinare in ordine crescente} = O (n)

Poiché non è richiesto alcuno spazio aggiuntivo, non ci vorrà spazio aggiuntivo .
Quindi, complessità spaziale: O (1)

Grazie per aver dedicato il tuo tempo a questo articolo. Spero che lo trovi utile e che ti dia una visione chiara.

Se hai ancora domande, non esitare a rispondere. Se lo trovi utile, condividilo con i tuoi colleghi. I tuoi applausi mi motivano a scrivere altri blog simili! 🙂