05 aprilie 2012

Backtracking si partitionarea unui numar in Python


nsol = 0.
nz = 0.
nr = []
N = 0.

def construct(nr_partitii, numar):
    global N, nr
    N = numar
    for i in range(nr_partitii):
        nr.append(0)

def is_zero():
    for i in range (len(nr)):
        if nr[i] == 0:
            return True
    return False

def init (k):
    nr[k] = -1

def succesor (k):
    if nr[k] < N:
        nr[k] += 1
        return True
    nr[k] -= 1
    return False

def valid (k):
    suma = 0.
    for i in range (k):
        suma += nr[i]
    if suma+nr[k] <= N:
        return True
    return False

def solutie (k):
    return k == len(nr)-1 and sum(nr)==N

def bt (k):
    init(k)
    global nsol, nz
    while succesor(k):
        if valid(k):
            if solutie(k):
                #print nr
                nsol += 1
                if is_zero():
                    #print nr
                    nz += 1
            elif k<len(nr)-1:
                bt(k+1)

print "Partitionarea unui numar"

construct(4,12)
bt(0)

print "Solutii: ",nsol
print nsol-nz,"combinatii de termeni nenuli"

Niciun comentariu: