[es] - Alg. Sve kombinacije cija suma daje zadati broj ?

urosk
BG

Član broj: 28668
Poruke: 41
*.sbb.co.yu.

Profil

Alg. Sve kombinacije cija suma daje zadati broj ?

^{16.02.2005. u 08:28}

Treba mi algoritam koji daje sve kombinacije iz odredjenog skupa brojeva ciji je zbir jednak nekom unapred zadatom broju,
recimo zbir koji trazim je 20 a moguci brojevi su iz skupa 1, 3, 4, 5, 10, 11, 15.... trebaju mi sve kombinacije bilo kog reda npr (15,1,4) (10,4,5,1) (11,4,5) (15,5)...

^{16.02.2005. u 08:28}

Alef
Viktor Kerkez
Novi Sad

Član broj: 505
Poruke: 188
*.041net.co.yu.

Profil

Re: Alg. Sve kombinacije cija suma daje zadati broj ?

^{16.02.2005. u 11:43}

Pošto tražiš samo algoritam, evo jedna mogućnost u Python-u.

Code:

from copy import copy

lista = []        # pomocna lista
kombinacije = []    # lista sa kombinacijama

def insert(lista):
    """ Proverava da li se ovaj *skup* brojeva koji prosledjujemo
    funkciji u obliku liste *lista* vec nalazi u listi *kombinacije* """

    for i in kombinacije:
        if set(i) == set(lista):  # set pretvara liste u skupovni tip
            return
    kombinacije.append(copy(lista))

def komb(sum, tren, skup):
    """
    sum  - suma koju trazimo
    tren - trenutna suma
    skup - skup brojeva koji dolazi u obzir za sumiranje
    """

    for i in skup:
        lista.append(i)
        tren += i
        if tren == sum:
            insert(lista)
            lista.pop()
            return
        elif tren > sum:
            lista.pop()
            return
        else:
            komb(sum, tren, skup)
            tren -= i
            lista.pop()

if __name__ == '__main__':
    sum = 20
    skup = [1, 3, 4, 5, 10, 11, 15]
    komb(sum, 0, skup)
    print kombinacije

^{16.02.2005. u 11:43}