Jupyter Snippet P4M TripletEnumerationExercise

Fast Python Exercise

The goal for this exercise is simple: given a list of numbers, enumerate all triplets of numbers contained in this list that sum to zero (without taking the same element twice out of the list).

This function can be implemented trivially as:

s3=lambda N: {(Ni,Nj,Nk) for i,Ni in enumerate(N) for j,Nj in enumerate(N) for k,Nk in enumerate(N)
               if len({i,j,k}) == 3 and Ni <= Nj <= Nk and Ni+Nj+Nk==0 }

Your task: Implement a fast function to compute the same set. This function should return the same result as s3(N) above (check for small lists N). Then check how long it takes for the following large list:

import random
random.seed(523529)
N = [random.randint(-10000,10000) for i in range(7777)]

Note that on the https://maxima.erc.monash.edu/ server can be done in basic python (without using external libraries) in under 5 seconds of CPU time. By importing appropriate libraries perhaps you can even do it in sub 1 second?

Testing

To check whether your method works, try some small instances and compare that they give the same result as the s3 function.

N20 = [random.randint(-15,15) for i in range (20)]
N50 = [random.randint(-100,100) for i in range(50)]

def myGenerator(N):
    for k,Nk in enumerate(N):
        for j,Nj in enumerate(N):
            for i,Ni in enumerate(N):
                if len({i,j,k}) == 3 and Ni <= Nj <= Nk and Ni+Nj+Nk==0:
                    yield (Ni,Nj,Nk)
def myFunc(N):
    return { triple for triple in myGenerator(N)}

S20 = s3(N20)
print(S20)
print("S20 has",len(S20),"elements and matches myFunc:",(S20==myFunc(N20)))

S50 = s3(N50)
print("S50 has",len(S50),"elements and matches myFunc:",(S50==myFunc(N50)))

{(-12, -3, 15), (-3, -3, 6), (-10, 0, 10), (-7, -3, 10), (-9, -1, 10), (-4, 1, 3), (-7, -1, 8), (-13, 3, 10), (-9, 3, 6), (-1, 0, 1), (-7, 1, 6), (-4, -4, 8), (-9, 1, 8), (-3, 0, 3)}
S20 has 14 elements and matches myFunc: True
S50 has 48 elements and matches myFunc: True