import random
#def nakljucni_sprehod_en2(matrika, k, l):  #vrne seznam prvega prihoda do vozlišča l iz vozlišča k; sprehod je naključen
#    koraki = 0
#    d = matrika.nrows()
#    rd = range(0,d)
#    if k == l:
#        sez3 = []
#        for j in rd:
#            if matrika[k,j] != 0:  #naredimo seznam sosednjih vozlišč
#                sez3.append(j)
#            else:
#                pass
#        c = random.choice(sez3)  #naključno izbere v kako vozlišče se premaknemo
#        k = c   #k označuje trenutno vozlišče
#        koraki += 1
#        while k != l:
#            sez3 = []
#            for j in rd:
#                if matrika[k,j] != 0:  #naredimo seznam sosednjih vozlišč
#                    sez3.append(j)
#                else:
#                    pass
#            c = random.choice(sez3)  #naključno izbere v kako vozlišče se premaknemo
#            k = c   #k označuje trenutno vozlišče
#            sez3 = []
#            koraki += 1
#    else:
#        while k != l:
#            sez3 = []
#            for j in rd:
#                if matrika[k,j] != 0:  #naredimo seznam sosednjih vozlišč
#                    sez3.append(j)
#                else:
#                    pass
#            c = random.choice(sez3)  #naključno izbere v kako vozlišče se premaknemo
#            k = c   #k označuje trenutno vozlišče
#            sez3 = []
#            koraki += 1
#    return koraki

#def nakljucni_sprehod_med_k_in_ostalimi(matrika, k):  #naredi nakjučni sprehod iz vozlišča k do vsakega; 1x
#    sez = []
#    d = matrika.nrows()
#    rd = range(0, d)
#    for i in rd:
#        sez.append(nakljucni_sprehod_en(matrika, k, i))
#    return sez

#def n_nakljucnih_sprehodov2(matrika, n):  #n-krat poženemo naključni sprehod iz vsakega vozlišča;
#    d = matrika.nrows()
#    sez = [0]*d
#    rd = range(0, d)
#    while n > 0:
#        for i in rd:
#            c = en_nsbc(matrika, i)
#            for i in rd:
#                sez[i] += c[i]
#        n -= 1
#    return sez

def nakljucni_sprehod_en(matrika, k, l,koraki=0):  #vrne seznam prvega prihoda do vozlišča l iz vozlišča k; sprehod je naključen
    d = matrika.nrows()
    rd = range(0,d)
    if k == l:
        sez3 = []
        for j in rd:
            if matrika[k,j] != 0:  #naredimo seznam sosednjih vozlišč
                sez3.append(j)
        c = random.choice(sez3)  #naključno izbere v kako vozlišče se premaknemo
        k = c   #k označuje trenutno vozlišče
        return nakljucni_sprehod_en(matrika,k,l,1)
    else:
        while k != l:
            sez3 = []
            for j in rd:
                if matrika[k,j] != 0:  #naredimo seznam sosednjih vozlišč
                    sez3.append(j)
            c = random.choice(sez3)  #naključno izbere v kako vozlišče se premaknemo
            k = c   #k označuje trenutno vozlišče
            koraki += 1
    return koraki

def en_nsbc(matrika, k):  #naredi nakjučni sprehod iz vsakega vozlišča do vozlišča k ; 1x
    sez = []
    d = matrika.nrows()
    for i in range(0, d):
        sez.append(nakljucni_sprehod_en(matrika, i, k))
    return sez

def n_nakljucnih_sprehodov(matrika, k, n):  #iz vsakega vozlišča n-krat poženemo naključni sprehod, ki se konča v k;
    d = matrika.nrows()
    sez = [0]*d
    rd = range(0, d)
    for j in range(0, n):
        c = en_nsbc(matrika, k)
        for i in rd:
            sez[i] += c[i]
    return sez

def nsbc_koncna(matrika, k, n):
    d = matrika.nrows()
    a = n * d
    s = n_nakljucnih_sprehodov(matrika, k, n)
    vsota = sum(s)
    return a/vsota