Domanda Ricerca sottomatrici in C

[silicio]

Ciao, qualcuno di voi conosce uno scritto breve o un articolo che spiega l'algoritmo per la ricerca di sottomatrici in C? O avete qualche consiglio o maniera di spiegarla?

Purtroppo è sempre stato un mio punto debole e mi devo mettere sotto per recuperare questa lacuna passata. Che ne pensate di questa bozza? Perdo troppe iterazioni o ne faccio troppe? (La sentinella e tutte le condizioni non le ho messe, era giusto per chiedere se effettivamente i cicli così lavorano.)

for(i=0; i<N; ++i){
        for(j=0; j<N; ++j){
            for(p=i; p<N-i; ++p){
                for(q=j; q<N-j; ++q){
                  //qua non ci ho messo niente, è giusto per far capire
                }
            }
        }
    }

Era un po' una porcheria e l'ho editato: questo penso compia tutti i casi possibili:

for(i=0; i<=N-1; ++i){
        for(j=0; j<=N-1; ++j){
            for(p=i; p<=N-1; ++p){
                for(q=j; q<=N-1; ++q){
                    printf(" %02d ", mat[p][q]);
                }
                printf("\n");
            }
            printf("\n");
        }
        printf("\n");
    }

 

[St3ve]

Prima di risponderti vorrei sapere cosa intendi per sottomatrice. La definizione formale dice che è consentito eliminare un qualsiasi sottoinsieme di righe e colonne, non necessariamente quelle ai bordi, ma forse tu sei interessato a qualcosa di diverso. Per esempio
$$\[ M = \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{bmatrix};\qquad A = \begin{bmatrix} 1 & 3 \end{bmatrix};\qquad B = \begin{bmatrix} 5 & 6 \\ 8 & 9 \end{bmatrix} $$\]Per te A è una sottomatrice di M? Oppure sei interessato solo alle sottomatrici fatte come B?

Per generare a A ho eliminato eliminato le ultime due righe e la colonna centrale di M, mentre per generare B ho eliminato la prima riga e la prima colonna di M.

Inoltre, cosa intendi per "ricerca"? Vuoi un algoritmo che ti stampa tutte le possibili sottomatrici o vuoi un algoritmo che prese due matrici ti dice se una è una sottomatrice dell'altra?

 

[nullptr]

@silicio: avendo $$\[M = \begin{bmatrix}1 & 2 & 3 & 4\end{bmatrix};$$\] vuoi ottenere $$\[ \begin{bmatrix} 1 \end{bmatrix};\qquad \begin{bmatrix} 2 \end{bmatrix};\qquad \begin{bmatrix} 3 \end{bmatrix};\qquad \begin{bmatrix} 4 \end{bmatrix};\qquad \begin{bmatrix} 1 & 2 \end{bmatrix};\qquad \begin{bmatrix} 2 & 3 \end{bmatrix};\qquad \begin{bmatrix} 3 & 4 \end{bmatrix};\qquad \begin{bmatrix} 1 & 2 & 3 \end{bmatrix};\qquad \begin{bmatrix} 2 & 3 & 4 \end{bmatrix};\qquad \begin{bmatrix} 1 & 2 & 3 & 4 \end{bmatrix}; $$\]?