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?