Preurejanje

Testi

testi-preurejanje.py

Naloga

Navodila so tokrat bistveno daljša kot rešitev naloge. Če boste programirali lepo, boste za obvezni del napisali 13 vrstic. Če jih bo več, razmislite, ali ste se lotili pametno. Bistvo te domače naloge je namreč delo s funkcijami ko programirate eno funkcijo, kličite funkcije, ki ste jih napisali pred tem, namesto da bi ponovno programirali iste stvari.

Ogrevalna naloga

Napišite funkcijo zamenjaj(s, a, b), ki zamenja elementa z indeksoma a in b v seznamu s. Funkcija ne vrne ničesar.

>>> s = ["Ana", "Berta", "Cilka", "Dani", "Ema"] >>> zamenjaj(s, 2, 4) >>> s ['Ana', 'Berta', 'Ema', 'Dani', 'Cilka']

Rešitev

def zamenjaj(s, a, b): s[a], s[b] = s[b], s[a]

Če je tole nalogo kdo rešil takole:

def zamenjaj(s, a, b): t = s[a] s[a] = s[b] s[b] = t

naj si naredi uslugo in začne programirati v Pythonu. To ni Python temveč C oziroma eden njegovih dialektov.

Obvezna naloga

Za obvezni del naloge boste napisali tri funckije.

Funkcija preuredi(s, menjave) dobi seznam in seznam menjav, podan v obliki parov. Funkcija izvede vse podane menjave tako, da kliče funkcijo zamenjaj, ki ste jo napisali za ogrevanje. Funkcija ne vrne ničesar.

Takole, recimo, bi zamenjali najprej drugi in tretji ter potem ničti in tretji element.

>>> s = ["Ana", "Berta", "Cilka", "Dani", "Ema"] >>> menjave = [(2, 3), (0, 3)] >>> preuredi(s, menjave) >>> s ['Cilka', 'Berta', 'Dani', 'Ana', 'Ema']

Funkcija urejen(s) dobi seznam in vrne True, če so elementi seznama urejeni po velikosti in False, če niso. (V tej funkckiji najbrž ne boste klicali funkcij, ki ste ju sprogramirali doslej.)

>>> urejen(['Cilka', 'Berta', 'Dani', 'Ana', 'Ema']) False >>> urejen(["Ana", "Berta", "Cilka", "Dani", "Ema"]) True

Funkcija ureja(s, menjave) vrne True, če podane menjave uredijo seznam s po velikosti. Funkcija naj kliče funkcije, ki ste jih sprogramirali doslej.

>>> s = ["Ema", "Berta", "Dani", "Cilka", "Ana"] >>> ureja(s, [(0, 4), (2, 3)]) True >>> ureja(s, [(0, 4)]) False >>> ureja(s, [(0, 4), (2, 3), (1, 2)]) False >>> s = ["Ana", "Berta", "Cilka", "Dani", "Ema"] >>> ureja(s, []) True

V prvem primeru smo dobili True, ker je v seznamu ["Ema", "Berta", "Dani", "Cilka", "Ana"] v resnici potrebno zamenjati ničti in četrti ter drugi in tretji element, da dobimo urejen seznam. Prav tako smo dobili True v zadnjem klicu, saj urejen seznam ostane urejen natančno takrat, ko ga pustimo pri miru.

Rešitev

def preuredi(s, menjave): for a, b in menjave: zamenjaj(s, a, b) def urejen(s): for a, b in zip(s, s[1:]): if a > b: return False return True def ureja(s, menjave): preuredi(s, menjave) return urejen(s)

Pri programiranju funkcija preuredi je lepo, če

• pokliče zamenjaj (tudi, če je ne bi in bi namesto tega v zanko napisali kar s[a], s[b] = s[b], s[a], se ne bi ravno pretegnili od tipkanja; in če
• razpakira par a, b kar v glavi zanke in ne kasneje.

Pri urejen ste bili mnogi pametni in ste urejenost preverjali kar z s == sorted(s). Prav, tu ni kaj. To je tako krajše kot hitrejše (v Pythonu). Moja rešitev pa je poučnejša. ;)

Če ste že uporabili sorted, pa, lepo prosim, ne tako

def urejen(s): if s == sorted(s): return True else: return False

To me neskončno frustrira. Ne vem, kolikokrat je potrebno na predavanjih povedati, da se to naredi takole:

def urejen(s): return s == sorted(s)

Pri zadnjih funkciji vas je zafrkavalo, da preuredi ne vrača rezultata, temveč spreminja seznam. Nekateri ste pisali

def ureja(s, menjave): return urejen(preuredi(s, menjave))

To ne deluje, ker preuredi ne vrne ničesar. Torej vrne None in v bistvu kličemo urejen(None).

Dodatna naloga

Napišite funkcijo nacrt(s), ki za podani seznam s vrne menjave, ki bi bile potrebne, za urejanje seznama.

Za dodatno (a ne prehudo) komplikacijo tokrat zahtevam, da funkcija nacrt ne spremeni seznama s.

Namig: poišči kak preprost algoritem urejanja, lahko tudi urejanje z mehurčki (bubble sort) in ga ustrezno dodelaj.

>>> s = ["Ema", "Berta", "Dani", "Cilka", "Ana"] >>> nacrt(s) [(0, 4), (2, 3)]

Naloga ima veliko rešitev in tudi sam nisem sprogramiral funkcije, ki bi vrnila tako lepo rešitev. Konkretno, za gornji seznam moja rešitev vrne načrt [(0, 1), (1, 2), (2, 3), (3, 4), (1, 2), (2, 3), (1, 2), (0, 1)].

Rešitev

Sprogramiramo preprost algoritem za urejanje seznama (kot sem povedal na predavanjih, tokrat nisem zameril, če ste ga odkod prepisali) in zabeležimo vsako narejeno menjavo. Tule je postopek, ki se imenuje urejanje z mehurčki. Več o teh rečeh boste izvedeli v drugem letniku.

def nacrt(s): s = s[:] perm = [] for i in range(len(s), 1, -1): for j in range(1, i): if s[j - 1] > s[j]: zamenjaj(s, j - 1, j) perm.append((j - 1, j)) return perm

Nekateri ste se kljub vsem dobrohotnim svarilom tega posla lotili z index in remove. Se res nimate prav nič radi?

Malo bolj dodatna naloga

Sestavi takšno funkcijo, kot jo zahteva dodatna naloga, vendar tako, da bo vedno vrnila najkrajši možni seznam menjav.

Rešitev

Če se noben element v seznamu ne ponovi, je rešitev relativno preprosta. Za vsakega ugotovimo kam sodi. Zapeljemo se čez seznam in v vsakem koraku prestavimo po en element tja, kjer mora biti (če ni že tam). To lahko v resnici naredimo z index. Število menjav bo enako, hm, dolžini seznama, od katerega odštejemo število ciklov, ki se pojavi v permutaciji. Ni važno; zapomnite si le, da se da minimalno število menjav čisto lahko izračunati.

Če se elementi ponavljajo ... zna biti, da je problem praktično nerešljiv. Rešitev seveda lahko poiščemo tako, da napišemo program, ki preišče praktično vse možnosti. Vendar lahko to že pri ne tako velikem seznamu traja grozno dolgo in pri vsakem dodatnem elementu se čas, recimo, podvoji. Takšnim problemom rečemo NP-polni problemi in jih boste v svojem študiju spoznali še veliko in to temeljiteje, kot si morda želite. ;)