Množice

Besede

besede, besede ... Kaj sploh je beseda? Osnovni delček komunikacije? Orožje? Zaporedje črk? Za nas bo beseda poljubno zaporedje znakov, torej niz!

1. podnaloga

Napišite funkcijo vse_crke(beseda, crke), ki pove, ali množica crke vsebuje vse črke, ki se pojavijo v podani besedi. Pri tem sme množica vsebovati tudi črke, ki se v besedi ne pojavijo.

  >>> vse_crke("AMFITEATER", set(["A", "M"]))
  False
  >>> vse_crke("AMFITEATER", set(["A", "M", "F", "I", "T", "E"]))
  False
  >>> vse_crke("AMFITEATER", set(["A", "M", "F", "I", "T", "E", "R"]))
  True
  >>> vse_crke("AMFITEATER", set(["A", "M", "F", "I", "T", "E", "R", "X",
  "O", "B", "L"]))
  True

Uradna rešitev

def vse_crke(beseda, crke):
    '''Vrne True, če množica crke vsebuje vse črke, ki se pojavijo v nizu
    beseda in False sicer'''
    return not (set(beseda) - set(crke))

2. podnaloga

Sestavite funkcijo podobna(beseda, sez_besed), ki kot argumenta sprejme besedo in seznam besed ter kot rezultat vrne tisto besedo iz sez_besed, v kateri se pojavi največ takih črk, ki se pojavijo tudi v dani besedi. Teh črk je seveda lahko tudi 0 ;-) !Vsako ujemajočo se črko štejemo le enkrat, tudi če se v obeh besedah pojavi večkrat. Funkcija naj deluje tako, da ne razlikuje med malimi in velikimi črkami. Če je takih besed več, vrnite tisto, ki je prej na vrsti v seznamu. Če take sploh besede ni, vrnite None. Predpostavite, da so v besedah samo črke.

  >>> besede = ["ana", "berta", "cilka", "dani", "ema", "fanči", "greta", "hilda"]
  >>> podobna("merjasec", besede)
  'berta'
  >>> podobna("zmaj", besede)
  'ema'
  >>> podobna("Krava", besede)
  'berta'

Ana in krava se ujemata v eni črki, namreč črki a in ne v dveh, pa čeprav imata po dva a-ja (tudi če bi napisali ana). Opomba: vsaka podobnost med Berto in merjascem je zgolj naključna.

Uradna rešitev

def podobna(beseda, sez_besed):
    '''Vrne besedo iz sez_besed, ki ima največ skupnih črk z besedo `beseda`'''
    bs = set(beseda.lower()) # množica vseh črk besede beseda (različnih seveda ;-) )
    naj_crk = 0
    naj_beseda = None # nimamo še najboljše besede
    for ena_beseda in sez_besed:
        skupnih = len(bs.intersection(set(ena_beseda.lower()))) # velikost preseka množic - število skupnih znakov
        if skupnih > naj_crk: # smo našli boljšega kandidata?
            naj_crk = skupnih
            naj_beseda = ena_beseda
    return naj_beseda # če ne bo ustreznih besed, bomo ostali pri None

3. podnaloga

Napišite funkcijo naj_raznolika(besede), ki kot argument prejme neprazen seznam besed in kot rezultat vrne besedo, ki ima največ različnih znakov. Male in velike črke upoštevajte kot iste znake - beseda "MamA" ima samo dva različna znaka. Če obstaja več besed z enakim številom različnih znakov, naj vrne zadnjo (glede na položaj v seznamu) med njimi.

  >>> besede = ["RABarbara", "izpit", "zmagA"]
  >>> naj_raznolika(besede)
  zmagA

Uradna rešitev

def naj_raznolika(besede):
     '''Vrne besedo in seznama besede, ki ima največ različnih znakov.'''
     naj_znakov = 0
     for en_niz in besede:
         crk = len(set(en_niz.lower())) # število različnih znakov
         if crk >= naj_znakov: # boljši kandidat (= ker hočemo zadnjega!)
              naj_znakov = crk
              naj_niz = en_niz
     return naj_niz

4. podnaloga

Program

   import urllib.request
   naslov = "http://splasho.com/upgoer5/phpspellcheck"
   naslov += "/dictionaries/1000.dicin"
   vir = urllib.request.urlopen(naslov)
   for vr in vir:
       vrstica = vr.decode()
       print(vrstica, end='')

izpiše po abecedi urejenih 1000 najpogostejših angleških besed. Napišite funkcijo naj_raznolika_ang_beseda(), ki vrne po abecedi urejen seznam vseh tistih med temi 1000 najpogostejšimi angleškimi besedami, ki imajo največ različnih črk.

Uradna rešitev

def naj_raznolika_ang_beseda():
     '''Vrne tiste besede med pogostimi angl. besedami, ki imajo največ različnih znakov.'''
     import urllib.request
     naslov = "http://splasho.com/upgoer5/phpspellcheck"
     naslov += "/dictionaries/1000.dicin"
     vir = urllib.request.urlopen(naslov)
     naj_znakov = 0
     for beseda in vir:
         en_niz = beseda.decode()[:-1] # odstranimo \n
         crk = len(set(en_niz.lower())) # število različnih znakov
         if crk == naj_znakov: # enakovredni kandidat
              naj_znakov = crk
              naj_nizi.append(en_niz)
         elif crk > naj_znakov: # boljši kandidat
              naj_znakov = crk
              naj_nizi = [en_niz]
     return naj_nizi # urejanje ni potrebno, ker so že besede urejene

Gimnazija

Janko ne mara matematike, je pa navdušen programer. In ker je v šoli dobil cel kup matematičnih nalog iz množic, jih bo rajši rešil tako, da bo napisal ustrezne programe v Pythonu.

1. podnaloga

Sestavite funkcijo vrni_tri(a, b), ki vrne nabor (A, B, C), kjer so A, B in C naslednje množice:

$$A = \{30n; n \in \mathbb{N}, n < a\}$$ $$B = \{n^3; n \in \mathbb{N}, 5n < b\}$$ $$C = \{5n; n \in \mathbb{N}, n^3 < a * b\}$$

Pri tem vemo, da velja $a \in \mathbb{N}$ in $b \in \mathbb{N}$

Uradna rešitev

def vrni_tri(a, b):
    '''vrne nabor treh matematično opisanih množic'''
    A = set()
    for n in range(1, a):
        A.add(30*n)
    B = set()
    n = 1
    while 5*n < b:
        B.add(n*n*n)
        n += 1
    C = set()
    n = 1
    while n*n*n < a*b:
        C.add(5*n)
        n += 1
    return (A, B, C)

2. podnaloga

Sestavite funkcijo racuni(A, B, C), ki vrne nabor (X, Y, Z), kjer so X, Y in Z naslednje množice:

$$X = A \cap B \cap C$$ $$Y = A \setminus (B \cup C)$$ $$Z = (A \setminus B) \cup C$$

  >>> racuni({2, 4, 6, 8, 10}, {1, 2, 3, 4}, {4, 6, 5})
  ({4}, {8, 10}, {4, 5, 6, 8, 10})

Uradna rešitev

def racuni(A, B, C):
    '''Računamo z množicami ...'''
    X = A & B & C
    Y = A - (B | C)
    Z = (A - B) | C
    return (X, Y, Z)

3. podnaloga

Sestavite funkcijo kartezicni(A, B), ki vrne nabor (X, Y), kjer sta X in Y množici:

$$X = A \times B$$ $$Y = B \times B$$

  >>> kartezicni({1, 2, 3}, {3, 4})
  ({(1,3), (1,4), (2,3), (2,4), (3,3), (3,4)}, {(3,3), (3,4), (4,3), (4,4)})

Uradna rešitev

def kartezicni(A, B):
    '''vrne nabor (X, Y), kjer X = A x B in Y = B x B'''
    X = set()
    for el1 in A:
        for el2 in B:
            X.add((el1, el2))
    Y = set()
    for el1 in B:
        for el2 in B:
            Y.add((el1, el2))
    return (X, Y)

Mirko si želi dekle

1. podnaloga

Mirko si ogleduje spisek vseh deklet, ki so mu všeč:

Ker sta s Slavkom tudi po vojni ostala "nerazdvojna druga", Mirko ne želi hoditi z nobeno od Slavkovih bivših deklet. Slavko mu je poslal spisek svojih bivših.

Pomagajte Mirku in sestavite funkcijo to_bo_moje_dekle(kandidatke, bivse) ki dobi dva seznama in vrne po abecedi urejen seznam deklet, med katerimi bo izbiral Mirko. A šarmerja, kot sta, imata izjemno dolga spiska. Zato bo "enostavna" rešitev

   for dekle in kandidatke:
      if dekle not in bivse:
          katere.append(dekle)

prepočasna. Sestavi torej metodo, kjer ne boš uporabil zanke (ne while in ne for, seveda pa tudi ne rekurzije)

   >>> to_bo_moje_dekle(['Jožica', 'Marjetka', 'Anja', 'Petra', 'Marija'],
                     ['Cilka', 'Petra', 'Pepca', 'Francka', 'Marija'])
   ['Anja', 'Jožica', 'Marjetka']

Uradna rešitev

def to_bo_moje_dekle(kandidatke, bivse):
    '''Vrne seznam možnih deklet za Mirka.
       Dejansko vrne seznam elementov tistih iz sezKand, ki
       niso v sezSlavko '''
    mno_kandidatke = set(kandidatke)
    mno_bivse = set(bivse)
    katere = mno_kandidatke - mno_bivse # razlika množic
    return sorted(katere) # želimo urejen seznam

Slovenske besede

1. podnaloga

Na http://bos.zrc-sazu.si/sbsj.html je 354.205 različnih besed iz gesel zbirke Besede slovenskega jezika. Program

   import urllib.request
   naslov = "http://bos.zrc-sazu.si/sbsj.html"
   vir = urllib.request.urlopen(naslov)
   vse = vir.read().decode()
   besede = vse.split('\n')[15:-13]

poskuša iz te datoteke narediti seznam vseh besed. Ampak kot vidimo, smo na začetku odrezali premalo. Prav tako se nismo znebili konca ... Sestavite funkcijo vrni_besedo(n), ki vrne n-ti besedo iz te datoteke. Besedo oklestite tudi zadnjih petih znakov, ki so '<br>\r'. Pri tem naj se n obnaša kot indeks v seznamu!

    >>> vrni_besedo(354204)
    žžžžk
    >>> vrni_besedo(354205)
    Traceback (most recent call last):
    ...
    IndexError: list index out of range
    >>> vrni_Besedo(0)
    a
    >>> vrniBesedo(-1)
    žžžžk

Uradna rešitev

def odst(niz):
    '''Iz niza odstrani <br>\r'''
    return niz[:-5]

def vrni_besedo(n):
    '''Vrne n-to besedo. Rešitev predpostavlja, da se besede začno v 15. vrstici in nehajo 13 vrstic pred koncem.
       Taka struktura je bila konec l. 2015
    '''
    import urllib.request
    naslov = "http://bos.zrc-sazu.si/sbsj.html"
    vir = urllib.request.urlopen(naslov)
    vse = vir.read().decode()
    besede = vse.split('\n')[15:-13]
    slečene = list(map(odst, besede))
    return slečene[n]

2. podnaloga

Sestavite funkcijo same_razlicne(zacetek), ki vrne množico vseh tistih slovenskih besed, ki se začno z nizom zacetek in jih sestavljajo same različne črke!

   >>> same_razlicne('mate')
   {'mate', 'maternik', 'materski', 'matec', 'matenski',
    'matek', 'maten', 'matevž', 'maternski', 'mater', 'materin'}

Uradna rešitev

def odst(niz):
    '''Iz niza odstrani <br>\r'''
    return niz[:-5]

def vrni_besede():
    '''Vrne vse besede is SSKJ. Rešitev predpostavlja, da se besede začno v 15. vrstici in nehajo 13 vrstic pred koncem.
       Taka struktura je bila konec l. 2015
       Namenoma ni uporabljano iskanje prve (a) oz. zadnje besede ('žžžžk')
    '''
    import urllib.request
    naslov = "http://bos.zrc-sazu.si/sbsj.html"
    vir = urllib.request.urlopen(naslov)
    vse = vir.read().decode()
    besede = vse.split('\n')[15:-13]
    slečene = list(map(odst, besede))
    return slečene

def enake_crke(niz):
    '''Ali je niz sestavljen iz samih različnih črk'''
    return len(niz) == len(set(niz))

def same_razlicne(zacetek):
    '''Vrne množico tistih slovenskih besed, ki so sestavljene i
       z samih enakih črk in se začno z zač'''
    vse_besede = vrni_besede()
    mn_besed = set()
    for beseda in vse_besede:
        if beseda.startswith(zacetek) and enake_crke(beseda):
            mn_besed.add(beseda)
    return(mn_besed)