Testi

Testi: testi-socialna-mreza.py

Naloga

V tej domači nalogi bomo delali z mrežami znancev, kot je recimo tale.

Predstavimo jo lahko z množico parov.

pari = {("Ana", "Berta"), ("Ana", "Greta"), ("Ana", "Helga"),
        ("Berta", "Cilka"), ("Berta", "Helga"),
        ("Cilka", "Dani"),
        ("Dani", "Ema"), ("Dani", "Greta"), ("Dani", "Helga"),
        ("Ema", "Fanči"), ("Ema", "Greta"), ("Ema", "Helga"),
        ("Fanči", "Iva"), ("Fanči", "Jana"), ("Fanči", "Klavdija"),
        ("Greta", "Helga")}

Zaradi preprostosti bomo vsak par navedli le enkrat in sicer po abecednem vrstnem redu. Napisali smo torej le par ("Ana", "Berta") in ne (tudi) ("Berta", "Ana").

Druga predstavitev je s slovarjem, katerega ključi so imena, pripadajoče vrednosti pa množice znancev.

mreza = {"Ana": {"Berta", "Greta", "Helga"},
         "Berta": {"Ana", "Helga", "Cilka"},
         "Cilka": {"Berta", "Dani"},
         "Dani": {"Cilka", "Ema", "Greta", "Helga"},
         "Ema": {"Dani", "Fanči", "Greta", "Helga"},
         "Fanči": {"Ema", "Iva", "Jana", "Klavdija"},
         "Greta": {"Ana", "Dani", "Ema", "Helga"},
         "Helga": {"Ana", "Berta", "Dani", "Ema", "Greta"},
         "Iva": {"Fanči"},
         "Jana": {"Fanči"},
         "Klavdija": {"Fanči"}
         }

Ker gre za slovarje in množice, je vrstni red tu nepomemben. Pač pa se zdaj vsak par v bistvu pojavi dvakrat: Berta je med Aninimi znanci, Ana pa med Bertinimi.

Tule je še ena manjša mreža.

Napišite naslednje funkcije.

Za oceno 6

• v_slovar(pari) kot argument prejme pare znancev (kot so gornji) in vrne slovar, kot je malo manj gornji.

• v_pare(mreza) naredi ravno obratno pretvorbo.

• n_znancev(mreza, n) prejme mrežo v obliki slovarja (druga predstavitev) in vrne množico imen vseh oseb, ki imajo natančno n znancev.

• osamljeni(mreza) vrne množico imen oseb, ki imajo le enega znanca.

• najbolj_znan(mreza) vrne ime osebe z največ znanci.

• skupni_znanci(mreza, oseba1, oseba2) vrne množico skupnih znancev podanih dveh oseb.

Rešitev

Funkcija v_slovar mora prek vseh parov (oseba1, oseba2) ter med znance prve osebe dodati drugo in obratno. Da se ne bomo hecali s ključi, ki še ne obstajajo, bomo uporabili defaultdict. Vrednosti morajo biti množice, torej potrebujemo defaultdict(set).

def v_slovar(pari):
    mreza = defaultdict(set)
    for oseba1, oseba2 in pari:
        mreza[oseba1].add(oseba2)
        mreza[oseba2].add(oseba1)
    return mreza

Zdaj pa nazaj. Funkcija v_pare gre prek slovarja. Potrebovali bomo osebo in njene znance. Gremo prek znancev in dodajamo pare (oseba, znanec), a le, če je oseba po abecedi pred znancem. Če ni, par mirno izpustimo, saj bomo v slovarju naleteli tudi na obratni par.

def v_pare(mreza):
    pari = set()
    for oseba, znanci in mreza.items():
        for znanec in znanci:
            if oseba < znanec:
                pari.add((oseba, znanec))
    return pari

Lahko bi naredili tudi obratno,

            if znanec < oseba:
                pari.add((znanec, oseba))

Lahko pa bi tudi oboje, vendar ni potrebno, saj se v slovarju pojavita obe kombinaciji.

Nekateri (mnogi!) so iz neznanega razloga sestavljali seznam in ga na koncu spremenili v množico.

def v_pare(mreza):
    pari = []
    for oseba, znanci in mreza.items():
        for znanec in znanci:
            if oseba < znanec:
                pari.append((oseba, znanec))
    mnozica_parov = set(pari)
    return mnozica_parov

To je čisto nepotrebno.

Funkcija n_znancev gre prek slovarja in v množico, ki si jo pripravimo v začetku, meče vsa imena oseb, ki imajo ravno prav znancev.

def n_znancev(mreza, n):
    o = set()
    for ime, znanci in mreza.items():
        if len(znanci) == n:
            o.add(ime)
    return o

Osamljeni so natančno tisti z enim znancem.

def osamljeni(mreza):
    return n_znancev(mreza, 1)

Najbolj znanega poiščemo tako, kot vedno iščemo kaj največjega ali najmanjšega.

def najbolj_znan(mreza):
    naj_znan = None
    for oseba, znanci in mreza.items():
        if naj_znan is None or len(znanci) > len(mreza[naj_znan]):
            naj_znan = oseba
    return naj_znan

Tokrat smo prvič (najbrž) napisali if naj_znan is None. Za preverjanje, ali je nek objekt ena None, naj bi se ne uporabljalo naj_znan == None temveč naj_znan is None. To deluje zato, ker je None samo eden; vsi None so si med seboj isti in ne le enaki. (Takšnim objektom se učeno reče singleton.) No, kar se tiče tega, bi še vedno lahko uporabili ==. Razlogi, zakaj je takšne objekte pravilneje primerjati z == so globji. Po drugi strani pa je zelo slaba ideja primerjati z is stvari, ki niso takšne sorte; a is 1234 navadno ni isto kot a == 1234 (in je navadno neresnično).

Zdaj pa še skupni_znanci. Množice! Imamo množico znancev prve osebe in množico znancev druge osebe. Kako se reče množici skupnih znancev? Presek vendar!

def skupni_znanci(mreza, a, b):
    return mreza[a] & mreza[b]

O, kakšne epe ste pisali namesto te funkcije!

Za oceno 7

• po_znancih(mreza) vrne slovar, katerega ključi so števila od 1 do len(mreza) - 1, pripadajoče vrednosti pa množice oseb, ki imajo toliko znancev. Za malo mrežo mora funkcija vrniti {1: {"D"}, 2: {"A", "B"}, 3: {"C"}}.

• priporocila(mreza) vrne množico parov, ki se med seboj ne poznajo, vendar imajo vsaj enega skupnega znanca. Par naj bo urejen po abecedi (prvi element naj bo po abecedi pred drugim).

• klika(mreza, imena) vrne True, če se vse osebe iz podane množice imen poznajo med seboj.

• najvec_skupnih(mreza) naj vrne imeni oseb, ki imata največ skupnih znancev. (Vrne naj terko, pri element naj bo po abecedi pred drugim.)

Rešitv

Najprej sestavimo slovar s samimi praznimi množicami. Potem gremo prek mreže in vsako osebo dodamo v ustrezno množico. Če vzamemo par oseba, znanci, je potrebno osebo dodati v množico po[len(znanci)].

def po_znancih(mreza):
    po = {}
    for i in range(1, len(mreza)):
        po[i] = set()
    for oseba, znanci in mreza.items():
        po[len(znanci)].add(oseba)
    return po

Da sestavimo množico priporočil najprej naredimo prazno množico. Nato gremo prek mreže; potrebovali bomo ime oseba in njene znance, torej for oseba1, znanci1 in mreza.items(). Za vsako osebo gremo prek vseh oseb v mreži. Da bi par dodali, mora veljati

• oseba1 je po abecedi pred oseba2 (oseba1 < oseba2),
• osebi se še ne poznata (oseba2 not in znanci1),
• osebi imata kakega skupnega znanca (skupni_znanci(mreza, oseba1, oseba2); spomnimo se, da je prazna množica neresnična).

Pa smo.

def priporocila(mreza):
    priporoci = set()
    for oseba1, znanci1 in mreza.items():
        for oseba2 in mreza:
            if oseba1 < oseba2 and oseba2 not in znanci1 and skupni_znanci(mreza, oseba1, oseba2):
                priporoci.add((oseba1, oseba2))
    return priporoci

Kliko lahko preverimo, recimo, takole:

def klika(mreza, imena):
    for ime in imena:
        if not imena - {ime} <= mreza[ime]:
            return False
    return True

Gremo prek vseh imen (for ime in imena) in preverimo, ali so vsa imena (iz domnevne klike) znanci te osebe. To bi se napisalo imena <= mreza[ime] (množica imena je podmnožica množice mreza[ime]), vendar moramo iz množice imen izločiti to ime, zato imena - {ime} <= mreza[ime]. Če to ni res vrnemo False, torej if not imena - {ime} <= mreza[ime]: return False.

Pri primerjanju ne smemo pozabiti enačaja: ne zanimajo nas le (stroge) podmnožice, temveč dopuščamo tudi, da oseba pozna natančno tiste osebe, ki so v (domnevni) kliki.

Običajno bi človek namesto not a <= b pisal a > b. Pri množicah pa ni tako. Če a ni podmnožica b, to nikakor ne pomeni, da je njena nadmnožica.

Še najvec_skupnih. To ni nič drugega kot še eno iskanje največjega po znanem vzorcu - s par dodatnimi pastmi.

def najvec_skupnih1(mreza):
    naj_par = None
    naj_skup = 0
    for oseba1 in mreza:
        for oseba2 in mreza:
            skup = len(skupni_znanci(mreza, oseba1, oseba2))
            if oseba1 < oseba2 and (naj_par is None or skup > naj_skup):
                naj_par = oseba1, oseba2
                naj_skup = skup
    return naj_par

Prva zanimiva vrstica je if. Po pravilih naloge mora biti prva oseba po abecedi pred drugo; če ni tako, nas par zanima. Če je, pa preverimo, ali je to prvi (zanimiv) par, naj_par is None ali pa je ima ta par več skupnih znancev kot najboljši par doslej (skup > naj_skup). Pri tem ne smemo pozabiti na oklepaje. Če jih izpustimo, je to enako, kot če bi pogoj zapisali kot (oseba1 < oseba2 and naj_par is None) or skup > naj_skup, kar bi bilo narobe na več načinov.

Za oceno 8

• neznanci(mreza, imena) vrne True, če se niti en par od oseb imena ne pozna med sabo in False, če kdo pozna koga.

• je_pokritje(mreza, imena) pove (tako, da vrne True ali False) ali velja tole: vsaka oseba je bodisi v množici imena bodisi pozna nekoga iz te množice.

• trikotniki(mreza) pove, kolikokrat se v mreži pojavi trojka oseb, ki se poznajo med seboj.

Rešitev

neznanci so samo obrnjena klika - pa še malo lažja, ker se nam ni potrebno ukvarjati z osebo samo (tisti - {ime}, ki smo ga imeli zgoraj).

def neznanci(mreza, imena):
    for ime in imena:
        if mreza[ime] & imena:
            return False
    return True

Če za katerokoli ime velja, da je med njegovimi znanci kdo iz podane množice imen, nemudoma vrnemo False.

je_pokritje za vsako osebo preveri, ali je na seznamu imen ali pa je katero od imen med njegovimi znanci.

def je_pokritje(mreza, imena):
    for oseba, znanci in mreza.items():
        if not (oseba in imena or imena & znanci):
            return False
    return True

Tidve funkciji sta bili za oceno 8 skoraj malo dolgočasni. Zato pa je preštevanje trikotnikov bolj zabavno. Najpreprostejša rešitev je kar preprosta: gremo čez vse trojke in če se osebe poznajo med seboj, je to trikotnik.

def trikotniki(mreza):
    vseh = 0
    for oseba1 in mreza:
        for oseba2 in mreza:
            for oseba3 in mreza:
                if oseba2 in mreza[oseba1] and oseba3 in mreza[oseba1] and oseba2 in mreza[oseba3]:
                    vseh += 1
    return vseh // 6

Zakaj pa vseh // 6? Ker smo vsak trikotnik šteli šestkrat: ABC, ACB, BAC, BCA, CAB CBA.

Zdaj pa malo razmislimo. Zanka oseba2 in mreza je nesmiselna, če vemo, da mora biti oseba2 znanec osebe1. Pač pojdimo le prek znancev oseba1, ne prek cele mreže.

def trikotniki(mreza):
    vseh = 0
    for oseba1 in mreza:
        for oseba2 in mreza[oseba1]:
            for oseba3 in mreza:
                if oseba3 in mreza[oseba1] and oseba2 in mreza[oseba3]:
                    vseh += 1
    return vseh // 6

S tem se je poenostavil tudi pogoj v if: pogoj oseba2 in mreza[oseba1] lahko pobrišemo, saj vemo, da bo resničen.

Podobno, le še bolj temeljito, opravimo z oseba3: zanimajo nas le tiste osebe, ki so znanci obeh, namreč prve in druge osebe.

def trikotniki(mreza):
    vseh = 0
    for oseba1 in mreza:
        for oseba2 in mreza[oseba1]:
            for oseba3 in mreza[oseba1] & mreza[oseba2]:                                         vseh += 1
    return vseh // 6

Pogoja sploh ne potrebujemo več! Vemo, da se osebe poznajo, saj jih že tako izbiramo. Potemtakem pa tudi zadnje zanke for ne potrebujemo, saj vnaprej vemo, kolikokrat bo prištela 1.

def trikotniki(mreza):
    vseh = 0
    for oseba1 in mreza:
        for oseba2 in mreza[oseba1]:
            vseh += len(mreza[oseba1] & mreza[oseba2])                               return vseh // 6

Tako smo (po daljši poti) prišli do nečesa, kar bi lahko razmislili že v začetku. Vzeti moramo neko osebo in vsakega njenega znanca. Trikotnikov, ki vsebujejo tidve osebi, je toliko, kolikor imata tidve osebi skupnih znancev.

Za oceno 9

• najmanjse_pokritje(mreza) vrne najmanjšo množico oseb, ki tvorijo pokritje (glej gornjo funkcijo je_pokritje). Namig: v modulu itertools je funkcija combinations, ki ti lahko pride prav. Naloga je lahka.

Rešitev

Res je lahka. V modulu itertools je funkcija combinations(s, n), ki zgenerira vse n-terke elementov iz s.

Najprej poskusimo, če se da mrežo pokriti z enim samim elementom. Če to ne gre, z dvema, sicer s tremi... Ko naletimo na kakšno podmnožico, ki je pokritje, jo vrnemo in iskanje se s tem ustavi.

def najmanjse_pokritje(mreza):
    from itertools import combinations
    imena = list(mreza)
    for i in range(1, len(mreza)):
        for podmnozica in combinations(imena, i):
            podmnozica = set(podmnozica)
            if je_pokritje(mreza, podmnozica):
                return podmnozica

Tale funkcija lahko vzame zelo veliko časa. Če mreža vsebuje n oseb, lahko zgenerira 2 ** n kombinacij. To je zelo veliko in hitro preveč za katerikoli računalnik. Zanimivo pa je, da boljšega algoritma za to ne poznamo. In, po drugi strani, nimamo dokaza, da ne obstaja.

Za oceno 10

• Vse gornje funkcije naj bodo napisane v eni vrstici, razen funkcij v_slovar, v_pare, najbolj_znan in najvec_skupnih. (Slednji dve je sicer preprosto napisati v eni vrstici, vendar se tega še nismo učili.)

Rešitev

Funkciji v_slovar in v_pare smo izpustili, ker sta grdi. Prva, recimo, lahko izgleda tako:

def v_slovar(pari):
    return {a: {b for aa, b in chain(pari, zip(*list(zip(*pari))[::-1])) if aa == a}
            for a, _ in chain(pari, (zip(*list(zip(*pari))[::-1])))}

ali tako:

def v_slovar(pari):
    return (lambda x: {a: {b for aa, b in x if aa == a} for a, _ in x})(pari | set(zip(*list(zip(*pari))[::-1])))

To je ogabno, nima smisla, nihče ne bi delal tako in ni poučno. Namen te naloge ni, da se važimo s tem, kaj znamo napisati v eni vrstici, temveč da vidimo, kako elegantna reč so izpeljani seznami, množice, slovarji in generatorji.

Funkcija n_znancev mora vrniti množico tistih imen, ki imajo n znancev ali, v Pythonu:

def n_znancev(mreza, n):
    return {ime for ime, znanci in mreza.items() if len(znanci) == n}

Funkcija osamljeni je bila že prej v eni vrstici, le n_znancev je poklicala. Če se odločimo, da ne velja klicati lastne funkcije, pa jo lahko na hitro spišemo tako, da poenostavimo n_znancev.

def osamljeni(mreza):
    return {ime for ime, znanci in mreza.items() if len(znanci) == 1}

Funkcije najbolj_znan ni bilo potrebno napisati v eni vrstici. Za motivacijo tistim, ki se malo dolgočasijo in ne vedo, kaj bi počeli, pa pokažimo, kako lahko s tisto zoprnijo vseeno na hitro opravimo z nečim, česar se (še?) nismo učili:

def najbolj_znan(mreza):
    return max(mreza, key=lambda x: len(mreza[x]))

Funkcija skupni_znanci je bila že prej v eni vrstici, saj je vrnila le presek. Kdor ni opazil, da naloga sprašuje po preseku, pa naj si pripiše posledice. :)

Funkcija po_znancih je klasičen izpeljan slovar.

def po_znancih(mreza):
    return {n: n_znancev(mreza, n) for n in range(1, len(mreza))}

Če si ne dovolimo klicati niti lastnih funkcij, n_znancev skopiramo sem noter.

Funkcijo priporocila brez težav, po vzorcu s predavanj, preobrnemo iz gornje oblike v eno samo izpeljano množico.

def priporocila(mreza):
    return {(a, b) for a in mreza for b in mreza if a < b and a not in mreza[b] and skupni_znanci(mreza, a, b)}

Funkcijo klika preobrnemo z lahkoto, če se spomnimo imenitne funkcije all:

def klika(mreza, imena):
    return all(imena - {ime} <= mreza[ime] for ime in imena)

Funkcije najvec_skupnih ni bilo potrebno napisati v eni vrstici, zato - spet brez komentarja - pokažimo, kako jo prepsto sestavimo z enakim trikom kot najbolj_znan.

def najvec_skupnih(mreza):
    return max(((a, b) for a in mreza for b in mreza if a < b),
               key=lambda x: len(skupni_znanci(mreza, *x)))

Funkcija neznanci je tako preprosta, da je že kar kičasto:

def neznanci(mreza, imena):
    return not any(mreza[ime] & imena for ime in imena)

Nobenega (not any) nepraznega preseka nočemo videti.

Funkcij je_pokritje lahko napišemo tako, da za vsako osebo preverimo, ali je med podanimi imeni ali pa je med imeni kdo od njenih znancev.

def je_pokritje(mreza, imena):
    return all(oseba in imena or znanci & imena for oseba, znanci in mreza.items())

Še malo krajšo različico pa dobimo, če preverjamo le tiste osebe, ki jih ni med imeni.

def je_pokritje(mreza, imena): return all(mreza[oseba] & imena for oseba in set(mreza) - imena)

Pa še trikotniki. Samo vsota, kaj pa drugega.

def trikotniki(mreza):
    return sum(len(skupni_znanci(mreza, a, b)) for a in mreza for b in mreza[a]) // 6