Permutation

A list is a permutation if it contains the numbers $1,2,\dots,n$ exactly once each. For example, the lists $[1]$, $[2,1]$ and $[3,1,2,4]$ are permutations.

In a file permutation.py, implement the class PermutationTracker with the following methods:

• append(number): add number to the end of the list
• check(): return True, if the list is a permutation, and False otherwise

The time complexity of both methods should be $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

Here the contents of the list change as follows:

• $[1]$ (is a permutation)
• $[1,4]$ (is not a permutation)
• $[1,4,2]$ (is not a permutation)
• $[1,4,2,3]$ (is a permutation)
• $[1,4,2,3,2]$ (is not a permutation)
• $[1,4,2,3,2,5]$ (is not a permutation)

You can test the efficiency of your solution using the following code. In this case too the code should finish almost immediately.

    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