Quale algoritmo posso utilizzare per trovare il subarray più grande all'interno di un array 2d con solo n numeri diversi?

Se la matrice ha una dimensione di n x m, allora ci sono circa n ^ 2 m ^ 2/4 sottoarray. Se ci sono k valori diversi, possiamo rappresentare ciascuno come un array di bit con k bit. Ciò prende ad esempio k ': = ceil (k / 64) parole a 64 bit.

È abbastanza facile calcolare ciascuno dei set di valori per n ^ 2 m ^ 2/4 sottoarray in un totale di n ^ 2 m ^ 2 k '/ 4 passi. Il numero di bit può essere contato in passi log2 (k), quindi abbiamo un totale di n ^ 2 m ^ 2 k 'log2 (k) / 4 operazioni. In questo caso, 10.000 * 10.000 * 1 * 6/4 = 150 milioni di passaggi. Quindi non un grosso problema. Diventa più interessante se i valori sono più grandi.

Tuttavia, questa ricerca di forza bruta sarebbe abbastanza inefficiente in questo caso (dove ogni cella contiene un numero casuale). Possiamo ragionevolmente calcolare la probabilità che un rettangolo di n numeri contenga k o meno numeri diversi, e che la probabilità scenda rapidamente se n diventa più grande di k. Quindi vorremmo evitare di controllare rettangoli davvero grandi. Ecco come suggerirei di procedere, per un array di n righe e m colonne, cercando il rettangolo più grande con al massimo k diversi numeri:

Gestiamo casi banali: k ≤ 0 significa nessuna soluzione, k ≥ numero di numeri diversi significa (1: n, 1: m) è la soluzione. Quindi trova la soluzione più semplice, che è solo il rettangolo più grande con un'area ≤ k. (Ad esempio, se l'array è 5x5 e k = 7, possiamo trovare banalmente un rettangolo di dimensione 6 ma non di dimensione 7). Lascia che la dimensione del rettangolo sia s ≤ k. Sia maxc (r)="il più grande c in cui non abbiamo dimostrato che un rettangolo con r righe e colonne c e meno di k numeri diversi non può esistere".

Dato un record s, abbiamo quindi bisogno di trovare un rettangolo che è più grande o dimostrare che non esiste. Troviamo una coppia (r, c) con il prodotto più piccolo r c tale che c ≤ maxc (r) e r c > S. Se tale coppia non esiste, allora abbiamo la soluzione ottimale. Altrimenti, cerchiamo un rettangolo di dimensioni r x c con k o meno numeri diversi. Se non viene trovato nessuno, allora impostiamo maxc (i) = min (maxc (i), c - 1) per tutto i ≥ r (non può esserci un rettangolo con r righe o più e con colonne c-1 o più) e prova ancora. Se viene trovato un rettangolo, lo registriamo, aumentiamo s, e riproviamo.

Potresti provare qualcosa del tipo:

1. Prendi l'intero array 2d
2. Rimuovi prima colonna / prima riga / ultima colonna / ultima riga
3. Impila ciascuno dei quattro sottoarray risultanti.
4. Memorizza il più grande che soddisfa la condizione, se è più grande di il più grande attualmente (se esiste).
5. Ripeti la procedura per ogni sottoarray nello stack

In questo modo avresti controllato ogni possibile sottoarray che puoi prendere dall'array di partenza, e assicurati di aver ottenuto il massimo possibile. Se lo vuoi un po 'più veloce, puoi tornare presto quando non ci sono più array più grandi di quelli attuali più grandi

Posso pensare a una tecnica ausiliaria che a volte può essere utile per una domanda correlata.

Si noti che questa tecnica ausiliaria non risolve la domanda principale . Non si dovrebbe usare questa tecnica se l'obiettivo è risolvere un determinato enigma dove la soluzione è garantita.

Questa tecnica ausiliaria è usata per dimostrare il contrario: che dato un array M-by-N, per ogni possibile sottotitolo A-by-B, si troveranno non meno di C etichette differenti. Questa tecnica risolve C quando viene dato A e B.

In altre parole, prova a risolvere un limite inferiore per C.

L'utilità in questa tecnica è che si può restituire un risultato negativo se qualcuno fa una query impossibile, o semplicemente come una regola euristica da utilizzare con altre tecniche di risoluzione.

1. I numeri A e B sono dati.
   • Se si utilizza questa tecnica come euristica, si possono provare dimensioni di sottoarray di forma quadrata, come (3, 3), (5, 5), (7, 7), ecc.
   • se si utilizza questa tecnica per verificare un risultato negativo per una determinata query, utilizzare (A, B) da quella query.
2. Converti ciascun numero in un bitvector di lunghezza N. (Ad esempio, N = 50 se al massimo 50 numeri diversi possono verificarsi nell'intero array.)
3. Definisci un operatore associativo "☀" come OR bit a bit di questi bitvector.
4. Definisci una "sfocatura" orizzontale (riga) (convoluzione) usando l'operatore associativo come segue, che opera su un sottoarray di 1-by-B.
   • Uscita (riga, colonna) = Ingresso (riga, colonna) ☀ Ingresso (riga, colonna + 1) ☀ Ingresso (riga, colonna + 2) ☀ ... ☀ Ingresso (riga, colonna + B - 1)
   • Nota: quando questo filtro viene applicato all'array di input della dimensione M-by-N, il risultato avrà la dimensione M-by- (N-B + 1).
5. Allo stesso modo, definisci una "sfocatura" verticale (in termini di colonne) (convoluzione), questa volta operando su un sottoarray di A-by-1.
   • Nota: quando il filtro verticale viene applicato a una matrice intermedia di dimensioni M-per- (N-B + 1), il risultato avrà dimensione (M-A + 1) -by- (N-B + 1 ).
6. Genera l'intero array "filtrato" come segue.
   • Lascia che IntermediateArray = HorizontalBlur (InputArray)
   • Consenti FilteredArray = VerticalBlur (IntermediateArray)
7. Ora, esamina FilteredArray per trovare l'elemento (bitvector) che ha il numero minimo di bit impostato .
   • Questo numero è la soluzione per C, per i valori dati di A e B.

Come ho avvertito sopra, questa tecnica non è una soluzione per il puzzle. È un tipo di tecnica di ottimizzazione delle prestazioni quando è necessario risolvere il puzzle ripetutamente, o su array di grandi dimensioni, o su alcune applicazioni pratiche (non per intrattenimento personale, apprendimento o concorsi di programmazione).

La tecnica è basata su una serie di tecniche di riconoscimento di immagini / modelli 2D come Immagine morfologica operazione .