Newsgroup: it.comp.programmare
Titolo: minomo per riga e colonna

Ho una matrice M x N
Mi occorre un algoritmo efficiente per calcolare per ogni riga se esiste un
elemento minimo che č anche il minimo della rispetiva colonna.
Ciao

Paul wrote:

Concettualmente puoi procedere cosi`: genera due matrici M x N i cui
elementi sono Booleani (true/false, 1/0) dove true significa per la prima
matrice "questo e` uno degli elementi minimi della sua riga" e per la
seconda "questo e` uno degli elementi minimi della sua colonna".  Lo
AND elemento per elemento di queste due matrici ti lascia una altra
matrice Booleana M x N i cui 1 corrispondono agli elementi di tuo
interesse (minimi sia della loro riga sia della loro colonna) che puoi
poi trasformare a tuo piacere se le tue esigenze presentazionali non
sono pienamente soddisfatte (ad esempio trovando gli indici delle
righe che non hanno neppure un 1 nella matrice risultante, o in altri
modi).  Questo approccio e` chiaramente O(M x N) quindi efficiente
in senso tecnico in termini di runtime (nessun algoritmo puo` essere
migliore di O(M x N) in quanto ogni elemento dell'input ovviamente
va esaminato!!!) mentre l'efficienza in termini di spazio ausiliario non
e` ovvia (ma qui devi chiarirci i tuoi trade-off spazio/tempo).  Il primo
vantaggio di questo approccio e` la semplicita` senza sacrificio di
efficienza (runtime... memoria da riesaminare).
Come pseudocodice supponiamo di avere per ogni oggetto-matrice
m gli ovvi attributi m.M ed m.N, accesso all'elemento con m[i, j] per
i fra 0 e M-1 e j fra 0 e N-1, e la possibilita` di costruire liste per
successive operazioni lalista.append(unvalore) di append-in-coda
e matrici con una fabbrica Matrice(M, N, 0) per costruire appunto
una matrice M x N con tutti gli elementi inizialmente a 0.
def dove_minimi_riga(m, indiceriga):
    minimo = m[indiceriga, 0]
    dove = [0]
    for j in range(1, m.N):
        elemento = m[indiceriga, j]
        if elemento < minimo:
            minimo = elemento
            dove = [j]
        elif elemento == minimo:
            dove.append(j)
    return dove
def ausiliaria_per_righe(m):
    ausiliaria = Matrice(m.M, m.N, 0)
    for i in range(0, m.M):
        dove_minimi = dove_minimi_riga(m, i)
        for j in dove_minimi:
            ausiliaria[i, j] = 1
    return ausiliaria
e gli ovvi duali per colonne.  L'intero approccio diviene dunque:
def per_paul(m):
    au_righe = ausiliaria_per_righe(m)
    au_colonne = ausiliaria_per_colonne(m)
    ausiliaria = Matrice(m.M, m.N, 0)
    for i in range(0, m.M):
        for j in range(0, m.N):
            ausiliaria[i, j] = au_righe[i, j] & au_colonne[i, j]
    return ausiliaria
e se ad esempio quello che ti serve e` la lista degli indici di
riga che non soddisfano la condizione (nessuno dei minimi
della riga e` anche il minimo della rispettiva colonna):
def brutte_righe(m):
    ausiliaria = per_paul(m)
    risultato = []
    for i in range(0, m.M):
        for j in range(0, m.N):
            if ausiliaria[i, j]: break
        else:
            risultato.append(i)
    return risultato
Il passaggio fra rappresentazioni di insiemi (di indici) come
liste e come mappe-di-bit (vettori di 0 e di 1) e` ovviamente
facile in entrambi i sensi, cosa ti convenga esattamente fare
dipende dalle esigenze di efficienza di tempo e di spazio,
nonche` di semplicita`.
Alex