Intersections of two lists

Question

Given two python lists a and b. These lists may intersect (It is possible that lists intersect more than once). An example:

a = [1,2,5,7,6,9,1,3,1,2,6,6,3,1,2,6,1,3]
b = [3,1,2]

There are 4 intersections:

 [1,2,5,7,6,9,1,3,1,2,6,6,3,1,2,6,1,3]
[3,1,2] [3,1,2] [3,1,2] [3,1,2]

For each intersection I can write equality: u + a + v == w + b + t

I need to write a function that returns lists u, v, w, t. For this example these lists are:

1. u = [3], v = []
 w = [], t = [5, 7, 6, 9, 1, 3, 1, 2, 6, 6, 3, 1, 2, 6, 1, 3]
2. u = [], v = []
 w = [1, 2, 5, 7, 6, 9, 1], t = [6, 6, 3, 1, 2, 6, 1, 3]
3. u = [], v = []
 w = [1, 2, 5, 7, 6, 9, 1, 3, 1, 2, 6, 6], t = [6, 1, 3]
4. u = [], v = [1, 2]
 w = [1, 2, 5, 7, 6, 9, 1, 3, 1, 2, 6, 6, 3, 1, 2, 6, 1], t = []

The following is a function I implemented (there is precondition: len(lhs)>= len(rhs)):

def get_additions(lhs, rhs):
 results = []
 szl = len(lhs)
 szr = len(rhs)
 i = 1 - szr
 while i < szl:
 a = max(0, i)
 b = max(0, -i)
 c = min(i + szr, szl)
 d = min(szr, szl - i)
 if (lhs[a:c] == rhs[b:d]):
 u = rhs[0:b]
 v = rhs[d:szr]
 w = lhs[0:a]
 t = lhs[c:szl]
 results.append((u, v, w, t))
 i += 1
 return results

How to make it better?

Answer 1

• at line if (lhs[a:c] == rhs[b:d]): parentheses are redundant

• you don't need to return whole list, you can return only iterator (remove results variable, change line results.append((u, v, w, t)) into yield u, v, w, t). After it you can always use this as list if needed (list(get_additions(a, b))) but usually you need only iterator.

• your variable i change from <1 - szr .. szl). You can use for i in xrange(1 - szr, szl): to do this

• at your description i can read about conditions u + a + v == w + b + t and len(lhs) >= len(rhs). You can write it in your code as assert

• at your description variables a, b means something else than in your code. It's not good idea. Your also use various conventions of variable naming (e.g. szr as size of right list and b as begining index of right list). You should define variables in the same way.

• personally i often remove variables like szr because len() of list is quite fast. It's your choice (you get less local variables but more len() calls).

• you always cut b[3:len(b)] into b[3:] and b[0:3] into b[:3]

After these changes your code could looks like

def get_additions(a, b):
 assert len(a) >= len(b)
 for i in xrange(1 - len(b), len(a)):
 a_left = max(0, i)
 b_left = max(0, -i)
 a_right = min(i + len(b), len(a))
 b_right = min(len(b), len(a) - i)
 if a[a_left:a_right] == b[b_left:b_right]:
 u = b[:b_left]
 v = b[b_right:]
 w = a[:a_left]
 t = a[a_right:]
 assert u + a + v == w + b + t
 yield u, v, w, t
if __name__ == "__main__":
 a = [1, 2, 5, 7, 6, 9, 1, 3, 1, 2, 6, 6, 3, 1, 2, 6, 1, 3]
 b = [3, 1, 2]
 for u, v, w, t in get_additions(a, b):
 print "u = %s, v = %s\nw = %s, t = %s\n" % (u, v, w, t)

• Gareth Rees: assert len(a) > len(b) seems wrong based on the OP's problem description.
• vaeta: Thx, add description one.