Ricerca del numero di sequenze possibili in un array, con condizioni aggiuntive

Question

Esiste una sequenza {a1, a2, a3, a4, ..... aN}. Una corsa è la parte continua strettamente crescente o strettamente decrescente della sequenza. Per esempio. Se abbiamo una sequenza {1,2,3,4,7,6,5,2,3,4,1,2} Abbiamo 5 possibili percorsi {1,2,3,4,7}, {7, 6,5,2}, {2,3,4}, {4,1} e {1,2}.

Dati quattro numeri N, M, K, L. Contare il numero di possibili sequenze di numeri N che ha esattamente M in esecuzione, ognuno del numero nella sequenza è minore o uguale a K e la differenza tra i numeri adiacenti è inferiore alla pari a L

La domanda è stata posta durante un'intervista.

Ho potuto solo pensare a una soluzione di forza bruta. Che cos'è una soluzione efficiente per questo problema?

Answer 1

Suppongo che intendiate per "soluzione di forza bruta" cosa potrei significare con "una soluzione semplice che coinvolge cicli nidificati su N, M, K, L"? A volte la soluzione semplice è abbastanza buona. Una delle volte in cui la soluzione semplice è abbastanza buona è quando non si ha una soluzione migliore. Un altro dei tempi è quando i numeri non sono molto grandi.

Con quello fuori dal mio petto vorrei scrivere i cappi nella direzione opposta, o qualcosa del genere. Intendo:

1. creare 2 strutture dati ausiliarie, uno per contenere gli indici dei numeri < = K, uno per gli indici dei numeri la cui differenza con i loro vicini è < = L.
2. Passare attraverso l'elenco di numeri e popolare le strutture di dati ausiliari precedenti.
3. Trova l'intersezione dei valori in queste 2 strutture di dati; questi saranno gli indici di luoghi interessanti per iniziare a cercare le corse.
4. Cerca in tutti i posti interessanti.

Fino a quando qualcuno non dimostra il contrario, questa è la soluzione più efficiente.

Answer 2

Utilizzare la programmazione dinamica. Per ciascun numero nella sottostringa, mantenere il conteggio separato delle sottosequenze massime crescenti e decrescenti. Quando aggiungi in modo incrementale un nuovo numero alla fine, puoi utilizzare questi conteggi per aggiornare i conteggi per il nuovo numero. Complessità: O (n^2)

Answer 3

Questo può essere riformulato come un problema di ricorrenza. Osserva il tuo problema come trovare # (N, M) (supponi che K e L siano fissi, che siano usati nelle condizioni di ricorrenza, quindi propagarsi di conseguenza). Ora inizia con le funzioni di conteggio più ristrette A (N, M; a) e D (N, M, a), dove A conta quei set con l'ultima corsa crescente, D conta quelli con ultima corsa decrescente, e a è il valore di l'ultimo elemento nel set.

Express # (N, M) in termini di A (N, M; a) e D (N, M; a) (è la somma su tutti ammessa a). Potresti notare che ci sono delle relazioni tra i due (come il riflesso A (N, M; a) = D (N, M; K-a)) ma ciò non importa molto per il calcolo, eccetto per il riempimento della tabella di velocità.

Ora A (N, M; a) può essere espresso in termini di A (N-1, M; w), A (N-1, M-1; x), D (N-1, M ; y) e D (N-1, M-1; z). L'idea è che se inizi con un set di dimensioni N-1 e conosci la direzione dell'ultima esecuzione e il valore dell'ultimo elemento, sai se aggiungere l'elemento a verrà aggiunto a un'esecuzione esistente o aggiungere una corsa. Quindi puoi contare il numero di possibili modi per ottenere quello che vuoi dalle possibilità del caso precedente.

Ti lascio scrivere questa ricorsione verso il basso. Nota che questo è il tuo account L (aggiungi solo quelli che obbediscono alla restrizione della distanza L) e K (cerca i casi finali).

Terminare la ricorsione usando il fatto che A (1, 1; a) = 1, A (1, x> 1; a) = 0 (e similmente per D).

Ora, poiché si tratta di una ricorsione multipla, accertarsi che l'implementazione memorizzi i risultati in una tabella e inizi provando la ricerca (comunemente chiamata programmazione dinamica).