from munkres import Munkres, print_matrix

#matriki v katerih bomo iskali minimalno in maksimalno porirejanje

matrika_A = [[82,83,69,92],
             [77,37,49,92],
             [11,69, 5,86],
             [ 8, 9,98,23]]

matrika_B = [[82,83,69,92],
             [77,37,49,92],
             [11,69,5,86],
             [8,9,98,23],
             [52,64,27,44]]


matrika_C = [[96, 85, 68, 71, 68, 62, 57, 98],
             [35, 96, 95, 54, 30, 37, 86, 88],
             [93, 88, 51, 79, 93, 79, 13, 96],
             [11, 16, 56,  2, 88, 79,  1, 93],
             [37, 78, 80, 15, 57, 81, 77, 13],
             [28, 89, 43, 31,  3, 18, 40, 92],
             [43, 87, 66, 35, 78, 35, 63, 45],
             [34, 30, 31, 96, 80, 71, 72, 32]]


def minimalno_prirejanje(matrika):
    '''funkcija poišce minimalno prirejanje matrike,ki kot razultat izpiše
    izpiše indekse in vrednosti elementov, ki predstavljajo rešitev problema,
    ter njihovo skupno vsoto.Vhodni podatek je seznam seznamov, , kjer posamezni
    podseznam predstavlja vrstico matrike'''
    
    m = Munkres()
    indeksi = m.compute(matrika) #Vrne seznam naborov, kjer posamezni
    #nabor predstavlja ineks elementa, ki je rešitv minimalnega prirejanja

    print_matrix(matrika, msg='Iskanje minimalnega prirejanja:')
    vsota = 0
    
    print ('Indeksi in vrednosti elementov, ki predstavljajo rešitev problema:')
    for vrstica, stolpec in indeksi: 
        vrednost = matrika[vrstica][stolpec]
        vsota += vrednost

        #izpis indeksov in vrednosti elementa, ki je rešitve problema
        print ('(%d, %d) -> %d' % (vrstica, stolpec, vrednost))
    print ('Rešitev minimalnega prirejanja: %d' % vsota)



def maksimalno_prirejanje(matrika):
    '''funkcija poišce maksimalno prirejanje matrike,ki kot razultat izpiše
    izpiše indekse in vrednosti elementov, ki predstavljajo rešitev problema,
    ter njihovo skupno vsoto. Vhodni podatek je seznam seznamov, , kjer posamezni
    podseznam predstavlja vrstico matrike'''
    
    pomozna = []
    # ustvarimo pomozno matriko, kateri bomo v vsaki vrstici poiskali najvecji element
    # in od tega elementa bomo odšteli vrednost posameznega elementa v vrstici
    
    for vrstica in matrika:
        pomozna_vrstica = []
        max_el = max(vrstica) #poišcemo najvecji element v vrstici
        for element in vrstica:
            pomozna_vrstica += [max_el - element] #vsakemu max elementu odštejemo posameznega iz vrstice
        pomozna += [pomozna_vrstica]

    
    m = Munkres()
    indeksi = m.compute(pomozna)
    
    #Vsi nadalnji koraki so enaki kot pri iskanju minimalnega prirejanaja 
    print_matrix(matrika, msg='Iskanje maksimalnega prirejanja:')
    vsota = 0
    print ('Indeksi in vrednosti elementov, ki predstavljajo rešitev problema:')
    for vrstica, stolpec in indeksi: 
        vrednost = matrika[vrstica][stolpec]
        vsota += vrednost
        
        print ('(%d, %d) -> %d' % (vrstica, stolpec, vrednost))
    print ('Rešitev maksimalnega prirejanja: %d' % vsota)


##TEST
print('\n--------PRIMER 1--------\n')
minimalno_prirejanje(matrika_A)
print('\n--------PRIMER 2--------\n')
minimalno_prirejanje(matrika_B)
print('\n--------PRIMER 3--------\n')
maksimalno_prirejanje(matrika_C)