[C] Trovare tutte le sottomatrici

[klarence]

Data una matrice NxN ho bisogno di trovare tutte le sue sottomatrici e fare delle verifiche su di esse (ma quest'ultima parte è semplice).

Come posso fare a trovare tutte le sottomatrici?

[gugoXX]

Io proverei con una funzione ricorsiva
che accetta in input una matrice e restituisce un array di matrici.
Pesante ma semplice (abbastanza insomma)

[klarence]

Io proverei con una funzione ricorsiva
che accetta in input una matrice e restituisce un array di matrici.
Pesante ma semplice (abbastanza insomma)


Potresti aiutarmi con la funzione da scrivere? Perchè con quello che faccio io riesco a generare solo alcuni tipi di sottomatrici...

[gugoXX]

Niente ricorsione,ho trovato un problema di duplicazione che non ho voglia di risolvere.
Vado in iterativo (parallellizzabile :D)
Lo scrivo in C#, perche' al C sono oramai allergico.
E metto anche tanto pseudocodice.
Niente che non si possa tradurre comunque.

penso sia O(N^2 LogN^2).
Fa pena, ma funziona.


public class Matrix
{
int Dim;
public float[,] Value;

public Matrix(int dim)
{
Dim=dim;
Value=new float[dim,dim];
}

public static List<Matrix> GimmeSub()
{
List<Matrix> ret = new List<Matrix>();
int Combinazioni = (1 << Dim);
for (int y = 0; y < Combinazioni; y++)
{
// Gli 1 del valore di y in binario dicono quali sono le righe da cancellare della sottomatrice
for (int x = 0; x < Combinazioni; x++)
{
// Gli 1 del valore di x in binario dicono quali sono le colonne da cancellare della sottomatrice

// Voglio tutte le sottomatrici o solo le sottomatrici quadrate?
// Se voglio solo le sottomatrici quadrate allora:
// Se il numero di 1 delle righe e' diverso dal numero di 1 delle colonne,
// allora skippo questo passo (altrimenti risulta una matrice non quadrata)

//Creo la sottomatrice senza le colonne marcate con 1
// E senza le righe marcate con 1
// Alla peggio e' di nuovo una paio di LOOP innestati, di nuovo un algoritmo di O (N^2)
ret.Add(questamatrice);


}
}
return ret;
}
}

[klarence]

Ti ringrazio per quello che hai scritto... ma purtroppo io faccio un corso di C... quindi molte cose che hai scritto sono per me incomprensibili...
Tieni anche presente che un eventuale problema di ''duplicazione'' per me non è un problema... l'importante per me è risolvere un problema, non è importante l'efficenza... potresti scrivermi il codice in c con la ricorsione? Scusa il disturbo

[gugoXX]

Ti ringrazio per quello che hai scritto... ma purtroppo io faccio un corso di C... quindi molte cose che hai scritto sono per me incomprensibili...
Tieni anche presente che un eventuale problema di ''duplicazione'' per me non è un problema... l'importante per me è risolvere un problema, non è importante l'efficenza... potresti scrivermi il codice in c con la ricorsione? Scusa il disturbo

Ciao, nessun disturbo, a parte che scrivere soluzioni ad esercizi non si puo', senno Cionci si arrabbia (a proposito, che fine ha fatto? Spero sia solo impegnatissimo)

Posso tentare di spiegarti l'algoritmo.
Se prendi la tua matrice NxN, per trovare tutte le sottomatrici possibili e' sufficiente cancellare (o tenere, e' il duale identico) tutte le possibili combinazioni di colonne per tutte le possibili combinazioni di righe.
Es: per dimensione pari a 3.
Prendiamo le righe p.es.
0. possiamo iniziare con il tenere tutte le righe.
1. Poi continuiamo cancellando solo la prima riga
2. poi solo la seconda
3. poi solo la prima e la seconda
4. poi solo la terza
5. poi solo la terza e la prima
6. poi solo la terza e la seconda
7. poi sia la terza, la seconda e la prima (inutile, significa che cancello tutte le righe, e non viene fuori nessuna matrice, a meno che anche la matrice "vuota" sia un risultato che ci interessa)


Se scriviamo un "codice binario" per queste informazioni, possiamo scrivere le seguenti:
0 - 000
1 - 001
2 - 010
3 - 011
4 - 100
5 - 101
6 - 110
7 - 111
Dove 0 significa che la riga la tengo, e 1 significa che la riga la cancello.
E guarda caso il valore a sinistra e' il valore decimale, mentre il valore a destra e' la sua rappresentazione in binario.

Ciascuna di queste combinazioni dobbiamo "usarla" per le relative combinazioni di tutte le colonne.
Al primo passo numero 4, quando abbiamo cancellato la terza riga, occorre che teniamo questa combinazione e che cancelliamo tutte le possibili combinazioni delle 3 colonne
che sono di nuovo 8, analoghe e identiche.

Cos'e' 8? E' esattamente 2^3, ovvero il numero di combinazioni possibili di 2 elementi (prendo la riga, non prendo la riga) su 3 posizioni (la nostra dimensione)

Riassumendo, 2 cicli annidati, uno per le righe e l'altro per le colonne, ciascuno dei quali va da 0 a 2^N
a ciascun passo quindi dovro' costruire la sottomatrice relativa trovata cancellando le righe corrispondenti agli "uni" della rappresentazione binaria del contatore sulle righe e cancellando le colonne corrispondenti agli "uni" della rappresentazione binaria del contatre sulle colonne.
Se non mi interessano le matrici rettangolari, che questo algoritmo genera, e' sufficiente che "salti" i passi che hanno un numero di "uni" delle righe diverso dal numero di "uni" delle colonne.

Fine, a parte che scrivere e maneggiare le matrici in C fa decisamente pena.

Se adotterai questo approccio ti consiglio di scrivere una funzione che, dato in ingresso una matriciona, la rappresentazione binaria delle righe da cancellare e quella delle colonne da cancellare, ti restituisce la sottomatrice corrispondente.

[klarence]

Proprio questa è la mia difficoltà.
Qui non si tratta di escludere sono 1 riga o 1 colonna.... devo escludere (o tenere) tutte le possibili combinazioni....

[klarence]

Allora ho risolto il problema di trovare le sottomatrici.... ora però ho un altro problema. L'esercizio mi chiede di trovare la sottomatrice quadrata di dimensione massima che ha la metà dei termini uguali a 1. Allora io, innanzitutto inizializzo la DIMENSIONE MASSIMA=0, quando trovo le sottomatrici, con un if chiedo che la sottomatrice sia quadrata (n. righe=n.colonne) e poi conto i termini = 1... e se n. termini=1 è la metà del numero totale di termini della matrice prendo in considerazione questa dimensione, e mi devo chiedere se dimensione>DIMENSIONE MASSIMA. Se dimensione>DIMENSIONE MASSIMA allora assegno a DIM. MAX il valore di dimensione.
Ora ecco il mio dubbio. Nell'esercizio la funzione deve restituire il valore ottenuto... ma il return DIM.MAX dove lo devo mettere? Io non vorrei che alla prima esecuzione del programma, e quindi al controllo della prima sottomatrice che trova, faccia il return ed esca dalla funzione...

[gugoXX]

Se hai fatto bene la prima parte di esercizio, troverai che l'insieme di tutte le sottomatrici di una matrice data e' un insieme finito e numerabile.
Al che la tua funzione dovra' numerare e controllare tutte le sottomatrici, prima di ritornare con la risposta richiesta.
Dovra scrivere un ciclo che controlli tutte le sottomatrici, e il return sara' all'esterno del ciclo, non in mezzo ad esso.

[klarence]

Se hai fatto bene la prima parte di esercizio, troverai che l'insieme di tutte le sottomatrici di una matrice data e' un insieme finito e numerabile.
Al che la tua funzione dovra' numerare e controllare tutte le sottomatrici, prima di ritornare con la risposta richiesta.
Dovra scrivere un ciclo che controlli tutte le sottomatrici, e il return sara' all'esterno del ciclo, non in mezzo ad esso.


edit ora è ok.

[klarence]

Allora ricapitoliamo e vediamo se è ok, mi sembra sempre tutto ok e poi ho delle incertezze. :muro:
Ho fatto tutte le combinazioni di righe e colonne attraverso un procedimento ricorsivo, una volta ottenute tutte le possibili combinazioni di righe e colonne devo dare gli array di righe e colonne ''in pasto'' ad un ciclo che controlli la sottomatrice e che veda se la sottomatrice rispetta quello che dico, in caso affermativo assegno al valore DIM.MAX il valore della dimensione della sottomatrice. Il programma completerà tutti i ''richiami'' della funzione e applicherà il discorso che ho appena fatto a tutte le possibili combinazioni di righe e colonne. ALL'ESTERNO DEL CICLO ci metto Return ''valore che mi serve'', che mi verrà restituito quando il programma ha controllato tutte le sottomatrici possibili.

E' ok?