Ana, Berta, Cilka in ostale znanke Programiranja 1 nakupujejo v neki spletni trgovini. Ana, recimo, je tam kupila stol, mizo, metlo in sesalec. Ema je kupila kroglo in frnikole. Celoten seznam (ehm, ne seznam, temveč nekaj drugega) je takšen:

stranke = {"Ana": {"stol", "miza", "metla", "sesalec"},
           "Berta": {"metla", "sesalec", "vedro"},
           "Cilka": {"flavta", "pesmarica"},
           "Dani": {"top", "krogla", "metla"},
           "Ema": {"krogla", "frnikole"},
           "Fanči": {"metla", "sesalec", "vedro"},
           "Greta": set(),
           "Helga": {"flavta"},
           "Iva": {"trobenta"}
          }

Napisali bomo nekaj funkcij, ki jih trgovina potrebuje za obdelavo svojih strank in priporočanje proizvodov.

Ogrevalna naloga

Podobnost med dvema strankama bi lahko "izmerili" tako, da bi izračunali število proizvodov, ki sta jih kupili obe. Tako bi bila podobnost med, recimo, Ano in Berto enaka 2, saj sta obe kupili metlo in sesalec. Vendar ta definicija ne bi bila dobra, ker so nekatere stranke kupile veliko proizvodov, torej je jasno, da bo tudi veliko skupnih. Po drugi strani pa sta dve stranki morda kupili le po en proizvod - vendar isti, torej sta si popolnoma podobni.

Podobnost zato definiramo kot število skupnih proizvodov deljeno s številom proizvodov, ki jih je kupila ena ali druga ali obe. Tako je podobnost med Ano in Berto enaka 2 / 5: obe sta kupili dva enaka proizvoda, vseh različnih proizvodov, ki jih je kupila ena ali druga ali obe, pa je pet (stol, miza, metla, sesalec in vedro).

Napiši funkcijo podobnost(stranke, stranka1, stranka2), ki kot argument dobi slovar, kakršen je gornji ter imeni dveh strank, ter vrne njuno podobnost.

  • Klic podobnost(stranke, "Ana", "Berta") mora vrniti 0.4,
  • klic podobnost(stranke, "Ana", "Cilka") vrne 0 in
  • klic podobnost(stranke, "Berta", "Fanči") vrne 1.

Poleg tega napiši funkcijo najpodobnejsa(stranke, stranka), ki prejme slovar strank in ime ene stranke, ter vrne ime najpodobnejše stranke.

Klic najpodobnejsa(stranke, "Ana") vrne "Fanči" ali "Berta".

Rešitev

Da brez preverlikih naporov napišemo prvo funkcijo, podobnost, moramo dovolj pozorno prebrati nalogo, da odkrijemo, da zahteva le, da delimo presek dveh množic z njuno unijo. Najlepše bo, da množici spravimo v dve spremenljivki, na primer nakup1 in nakup2, ter izračunamo in vrnemo, kar je treba.

def podobnost(stranke, stranka1, stranka2):
    nakup1, nakup2 = stranke[stranka1], stranke[stranka2]
    return len(nakup1 & nakup2) / len(nakup1 | nakup2)

Funkcija najpodobnejsa pa je klasika, ki jo obračamo že, odkar se poznamo.

def najpodobnejsa(stranke, stranka):
    najpodobnost = najpodobnejsa = None
    for stranka2 in stranke:
        if stranka2 != stranka and (
                najpodobnost == None or
                podobnost(stranke, stranka, stranka2) > najpodobnost):
            najpodobnost, najpodobnejsa = podobnost(stranke, stranka, stranka2), stranka2
    return najpodobnejsa

Ker to tolikokrat počnemo, obstajajo tudi različne bližnjice, o katerih se bomo učili prihodnje leto. Ena je, recimo

def najpodobnejsa(stranke, stranka):
    return max([x for x in stranke if x != stranka], key=lambda x: podobnost(stranke, stranka, x))

Obvezna naloga

Napiši funkcijo vsi_artikli(stranke), ki vrne množico vseh reči, ki jih je kdaj kdo kupil. Klic vsi_artikli(stranke) - pri čemer je stranke gornji slovar - tako vrne {"stol", "miza", "metla", "sesalec", "vedro", "flavta", "pesmarica", "top", "krogla", "frnikole", "trobenta"}.

Namig: slovar ima metodi items in values. Vsaj ena od njiju ti lahko pride prav pri tej in drugih funkcijah.

Napiši funkcijo kupljeno_poleg(stranke, stvar), ki vrne množico stvari, ki so jih kupile stranke, ki so kupile podano stvar. Klic kupljeno_poleg(stranke, "krogla") vrne {"top", "metla", "frnikole"}, saj so stranke, ki so kupile kroglo, kupovale tudi topove, metle in frnikole.

Napiši še funkcijo nasveti, ki vrne slovar, katerega ključi so vse stvari, ki jih je kdaj kdo kupil, vrendosti pa množice stvari, ki so jih kupili poleg njih. Tako nasveti(stranke) vrne

{'krogla': {'metla', 'top', 'frnikole'},
 'metla': {'sesalec', 'vedro', 'miza', 'krogla', 'stol', 'top'},
 'stol': {'metla', 'sesalec', 'miza'},
 'flavta': {'pesmarica'},
 'pesmarica': {'flavta'},
 'frnikole': {'krogla'},
 'sesalec': {'metla', 'vedro', 'stol', 'miza'},
 'vedro': {'metla', 'sesalec'},
 'top': {'krogla', 'metla'},
 'miza': {'metla', 'sesalec', 'stol'}}

Rešitev

Naloga vsi_artikli sprašuje po uniji vseh množic, ki so shranjene kot vrednosti v slovarju.

Gremo torej čez stranke.values() in vse vrednosti "priunijamo" v množico, ki jo na koncu vrnemo.

def vsi_artikli(stranke):
    vse = set()
    for nakup in stranke.values():
        vse |= nakup
    return vse

Funkcija kupljeno_poleg je na las podobna, le da dodaja le tiste množice, ki vsebujejo podano stvar. Poleg tega moramo na koncu iz množice odstraniti to reč. Za to bi lahko uporabili remove, vendar bi ta deloval le, če množica dejansko vsebuje to stvar. Če je ne (in je množica torej prazna), bi javil napako. Zato od množice raje odštejemo množico, ki vsebuje podano stvar. Odštevanje bo vedno delovalo - četudi množica te stvari morda sploh ne vsebuje.

def kupljeno_poleg(stranke, stvar):
    poleg = set()
    for nakup in stranke.values():
        if stvar in nakup:
            poleg |= nakup
    return poleg - {stvar}

Pazite: poleg - {stvar} in ne poleg - stvar. Od množice odštevamo množice, ne elementov.

Funkcija nasveti za vsako stvar pokliče funkcijo kupljeno_poleg in v novi slovar dodaja stvar kot ključ in rezultat funkcije kupljeno_poleg kot vrednost.

def nasveti(stranke):
    n = {}
    for stvar in vsi_artikli(stranke):
        poleg = kupljeno_poleg(stranke, stvar)
        if poleg:
            n[stvar] = poleg
    return n

Dodatna naloga

Napiši funkcijo najpodobnejse(stranke, stranka, k), ki dela podobno kot funkcija najpodobnejsa, le da vrne množico k najpodobnejših strank.

Napiši tudi funkcijo vse_najpodobnejse(stranka, stranka), ki dela podobno kot funkcija najpodobnejsa, le da vrača množico, v kateri so vse stranke, ki si delijo prvo mesto po podobnosti. Tako klic najpodobnejsa(stranke, "Ana") vrne {"Berta", "Fanči"}, saj sta obe najpodobnejši (to je, enako podobni) Ani.

Rešitev

Najpodobnejših k bomo poiskali tako, da bomo uredili stranke po padajoči podobnosti in vrnili prvih k. Po padajoči podobnosti jih lahko uredimo, recimo, tako da sestavimo seznam parov (-podobnost, stranka). Ko jih uredimo, bodo urejene po naraščajoči negativni podrobnosti (finta!). Potem iz tega slovarja poberemo le stranke.

Opis je malo zapleten, program pa bo tem, ki vas zanimajo dodatne naloge, najbrž jasen:

def najpodobnejse(stranke, stranka, k):
    s = [(-podobnost(stranke, stranka, stranka2), stranka2)
         for stranka2 in stranke
         if stranka2 != stranka]
    return {x[1] for x in sorted(s)[:k]}

Funkcijo vse_najpodobnejse bi lahko rešili tako, da bi poiskali največjo podobnost, nato pa šli ponovno čez stranke in nabrali te, ki imajo takšno podobnost.

Vendar je taka rešitev za nas prelahka. :) Napodobnejše bomo spravljali v množico najpodobnejsa. Kadar bomo naleteli na stranko, ki je podobnejša od najpodobnejše, bomo sestavili novo množico, najpodobnejsa = {stranka2}. Kadar pa bomo naleteli na stranko, ki si deli največjo podobnost, jo bomo dodali v množico, najpodobnejsa.add(stranka2).

def vse_najpodobnejse(stranke, stranka):
    najpodobnost = najpodobnejsa = None
    for stranka2 in stranke:
        if stranka2 == stranka:
            continue
        pod = podobnost(stranke, stranka, stranka2)
        if najpodobnost == None or pod > najpodobnost:
            najpodobnost = pod
            najpodobnejsa = {stranka2}
        elif pod == najpodobnost:
            najpodobnost = pod
            najpodobnejsa.add(stranka2)
    return najpodobnejsa

Krajše rešitve

Ker smo se kmalu po tej domači nalogi naučili uporabljati izpeljane sezname, množice in slovarje, rešimo naloge še na ta način, v enovrstičnih funkcijah.

def podobnost(stranke, stranka1, stranka2):
    return len(stranke[stranka1] & stranke[stranka2]) / len(stranke[stranka1] | stranke[stranka2])

def najpodobnejsa(stranke, stranka):
    return max([x for x in stranke if x != stranka], key=lambda x: len(stranke[stranka] & stranke[x]) / len(stranke[stranka] | stranke[x]))

def vsi_artikli(stranke):
    return reduce(set.union, stranke.values(), set())

def kupljeno_poleg(stranke, stvar):
    return reduce(set.union, (x for x in stranke.values() if stvar in x), set()) - {stvar}

def nasveti(stranke):
    return {stvar: kupljeno_poleg(stranke, stvar) for stvar in vsi_artikli(stranke) if kupljeno_poleg(stranke, stvar)}

Funkcijo najpodobnejse smo v bistvu že rešili v eni vrstici (zgoraj), le prvo vrstico je potrebno stlačiti v drugo.

Funkcije vse_najpodobnejse pa ne bomo tlačili v eno vrstico, saj bi bila predolga (brez kakega trika, ki pa se ga v tem trenutku ne spomnim).

Že funkcija nasveti ni prav lepa, ker za vsako stvar dvakrat pokliče kupljeno_poleg. Rešimo se lahko z generatorjem znotraj generatorja.

def nasveti(stranke):
    return {stvar: poleg for stvar, poleg in ((stvar, kupljeno_poleg(stranke, stvar)) for stvar in vsi_artikli(stranke)) if poleg}

Ampak to je grdo.

마지막 수정됨: 월요일, 2 3월 2026, 9:28 PM