Skip to content

Instantly share code, notes, and snippets.

@ptigas
Created May 29, 2012 17:45
Show Gist options
  • Save ptigas/2829701 to your computer and use it in GitHub Desktop.
Save ptigas/2829701 to your computer and use it in GitHub Desktop.
intersection algorithm in python
def intersection( *A ) :
res = []
while True :
# check if the heads are the same
all_same = True
for i in range(1, len(A)) :
if len(A[i]) > 0 and len(A[i-1]) > 0 and A[i-1][0] == A[i][0] :
pass
else :
all_same = False
if all_same :
# append to intersection set
res.append(A[0][0])
# remove from all arrays the intersected item
for i in range(len(A)) :
if len(A[i]) > 0 :
tmp = A[i][0]
while A[i] != [] and A[i][0] == tmp :
A[i].pop(0)
else :
return res
else :
# find the array with minimum head ...
min_i = 0
for i in range(len(A)) :
if len(A[i]) == 0 or len(A[min_i]) == 0 :
return res
if A[i][0] < A[min_i][0] :
min_i = i
# and remove it's head item
A[min_i].pop(0)
# Example code
A = [1,2,3,4,4.1,4.2,4.3,5,7,8,100]
B = [2,5,7,8]
C = [2,3,4,5,6,7,8]
print intersection( A, B, C )
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment