Menjave

Testi

Testi: testi-menjave.py

Obvezna naloga

Napiši funkcijo zamenjaj(s, i, j), ki v podanem s zamenja i-ti in j-ti element. Funkcija spreminja podani seznam in ne vrne ničesar.

Napiši tudi funkcijo zamenjan(s, i, j), ki vrne seznam, ki vsebuje iste elemente kot s, le da sta i-ti in j-ti element zamenjana. Funkcija ne spreminja podanega seznama.

Rešitev

def zamenjaj(s, i, j):
    s[i], s[j] = s[j], s[i]

def zamenjan(s, i, j):
    t = s[:]
    zamenjaj(t, i, j)
    return t

Drugo funkcijo je daleč najpreprosteje napisati tako, da skopiramo seznam in pokličemo prvo funkcijo. Ta trik ste (vsaj nekateri) spoznali tudi na vajah.

Dodatna naloga

Napiši funkcijo uredi(s), ki prejme seznam s in vrne seznam menjav (torej seznam parov indeksov), ki so potrebne, da uredimo seznam. Za seznam [5, 2, 8, 1] lahko vrne, recimo, zaporedje, [(0, 1), (2, 3), (1, 2), (0, 1)]. Funkciji ni potrebno vrniti najkrajšega možnega zaporedja. Možnih rešitev je (dobesedno) neskončno.

Nasvet: najpreprostje bo, če sprogramiraš kak preprost algoritem za urejanje seznamov in si ob urejanju hraniš spremembe. Zadoščalo bo celo že urejanje z mehurčki.

Seveda pa si izzvan(a) tudi, da sestaviš najkrajše možno zaporedje (čeprav ga naloga ne zahteva). Namig: imelo bo len(s) - 1 menjav.

Rešitev

Tole pa v resnici ni bila naloga iz tekoče snovi, temveč bolj iz prorgamiranja "kar tako". Poiskati ste morali poljuben postopek, s katerim lahko uredite seznam elementov, ga sprogramirati in si beležiti menjave.

def uredi(s):
    t = s[:]
    menjave = []
    for i in range(len(t)):
        for j, (e, f) in enumerate(zip(t, t[1:])):
            if e > f:
                menjave.append((j, j + 1))
                zamenjaj(t, j, j + 1)
    return menjave

Pri tem v začetku ne smemo pozabiti skopirati seznama, saj bomo sicer spreminjali seznam, ki smo ga dobili kot argument, tega pa ne smemo početi.

V namig sem - ne popolnoma pravilno! - napisal, da bo imelo najkrajše zaporedje len(s) - 1 menjav. Drži le, da nikoli ne potrebujemo več kot len(s) - 1 menjav, lahko pa jih tudi manj.

Recimo, da je potrebno tiste, ki so bili prej na mestih z indeksi 1, 2, 3, 4, 5 (morda v kakem jeziku, kjer začnemo šteti z 1, ne 0) prestaviti na mesta 2, 5, 4, 3, 1. Da boste lažje razumeli, poglejte sliko na Wikipediji. Če je tako, lahko zamenjamo 5 in 1 ter 2 in 5, potem pa 3 in 4. Skupaj tri menjave. V splošnem je število menjav enako številu elementov minus število ciklov.

Če ne razumete (in verjetno ne:)), to jemljite kot dober argument, zakaj morajo biti računalnikarji dobri v matematiki. Da razumejo tudi takšne stvari.