Permutaatio

Lista on permutaatio, jos se sisältää jokaisen luvun $1,2,\dots,n$ kerran, missä $n$ on listan koko. Esimerkiksi listat $[1]$, $[2,1]$ ja $[3,1,2,4]$ ovat permutaatioita.

Toteuta tiedostoon permutation.py luokka PermutationTracker, jossa on seuraavat metodit:

• append(number): lisää luku listan loppuun
• check(): palauta True, jos lista on permutaatio, ja muuten False

Kummankin metodin tulee toimia ajassa $O(1)$.

class PermutationTracker:
    def __init__(self):
        # TODO

    def append(self, number):
        # TODO

    def check(self):
        # TODO

if __name__ == "__main__":
    tracker = PermutationTracker()

    tracker.append(1)
    print(tracker.check()) # True

    tracker.append(4)
    print(tracker.check()) # False

    tracker.append(2)
    print(tracker.check()) # False

    tracker.append(3)
    print(tracker.check()) # True

    tracker.append(2)
    print(tracker.check()) # False

    tracker.append(5)
    print(tracker.check()) # False

Tässä listan sisältö muuttuu seuraavasti:

• $[1]$ (on permutaatio)
• $[1,4]$ (ei ole permutaatio)
• $[1,4,2]$ (ei ole permutaatio)
• $[1,4,2,3]$ (on permutaatio)
• $[1,4,2,3,2]$ (ei ole permutaatio)
• $[1,4,2,3,2,5]$ (ei ole permutaatio)

Voit tutkia ratkaisusi tehokkuutta seuraavan testin avulla. Tässäkin tapauksessa koodin tulisi antaa vastaus välittömästi.

    tracker = PermutationTracker()
    total = 0
    for i in range(10**5):
        if i%2 == 0:
            tracker.append(i + 2)
        else:
            tracker.append(i)
        if tracker.check():
            total += 1
    print(total) # 50000