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?

  • 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)
  • 2
    assert len(a) > len(b) seems wrong based on the OP's problem description. – Gareth Rees May 10 '16 at 7:50
  • Thx, add description one. – vaeta May 10 '16 at 14:14

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.