Permutaatiot

Sinulle annetaan kaksi listaa $A$ ja $B$, joissa molemmissa on lukujen $1 \dots n$ jokin permutaatio (eli molemmat listat sisältävät luvut $1 \dots n$ jossain järjestyksessä).

Tehtäväsi on laskea, moniko luvuista $1 \dots n$ esiintyy aiemmin listalla $A$ kuin listalla $B$. Tavoitteena on, että algoritmin aikavaativuus on $O(n)$.

Toteuta tiedostoon permutations.py funktio count, joka palauttaa halutun tuloksen.

def count(a, b):
    # TODO

if __name__ == "__main__":
    print(count([1,2,3], [1,2,3])) # 0
    print(count([2,3,4,1], [1,2,3,4])) # 3
    print(count([4,7,3,1,6,2,5], [5,6,1,2,4,3,7])) # 3
    print(count([5,4,9,1,8,3,2,6,7], [6,2,8,4,9,1,5,7,3])) # 5

Selitys: Ensimmäisessä esimerkissä molemmat listat $A$ ja $B$ ovat identtiset. Siksi mikään luku ei esiinny aikaisemmin listalla $A$ kuin $B$. Toisessa esimerkissä luvut $2$, $3$ ja $4$ esiintyvät listalla $A$ aiemmalla indeksillä kuin listalla $B$.