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