Intersection in Python keeping order

Question

I want to find intersection of two lists with original order. So if

a = [2, 3, 5, 6]
b = [17, 28, 2, 8, 0, 3]

I need [2, 3]. But for [3, 2, 5, 6] and [17, 28, 2, 8, 0, 3] I need [2].

How I can get it?

Answer 1

def inter(a,b):
    c = []
    for num in a:
        if num in b and (not len(c) or b.index(c[-1]) < b.index(num)):
            c.append(num)
    return c

Answer 2

You will have to loop over one list, searching the element in the other list, and only search the other list from that point for any following element.

Code could be:

a = [3, 2, 5, 6]
b = [17, 28, 2, 8, 0, 3]

def intersect(a,b):
    result = []
    ix = 0
    for x in a:
        try:
            ix = b[ix:].index(x)
            result.append(x)
        except ValueError:
            pass
    return result

print(intersect(a, b))

It gives:

[3]

NB: if you want [2], just use intersect(b, a)

Answer 3

This is more of a research problem than a StackOverflow question...

The phrase to search for is "longest common subsequence problem". Once you've found an algorithm that suits your situation, it will probably be clearer how to translate it into Python, or you can ask more targeted questions here.

Answer 4

a = [7, 8, 6, 6, 8, 10, 3, 3]
b = [7, 4, 10, 8, 7]

def magic(a, b):
    result = []

    # early abort
    if len(a) == 0 or len(b) == 0:
        return result

    try:
        index_b = b.index(a[0])
        result.append(b[index_b])
        # a[0] was found in b at index index_b. Disregard any items before index_b in the future.
        # And since we found a[0], we can remove it from our search list a.
        # continue with next search
        return result + magic(a[1:], b[index_b+1:])
        
    except ValueError:
        # a[0] is not in b. continue with next item in a.
        # No need for new code, just do the same function again for a shorter a.
        return result + magic(a[1:], b)

print(magic(a,b))

This prints [7,8]. I hope the code is self-explanatory.

It fulfills your test case 1:

a = [2, 3, 5, 6]
b = [17, 28, 2, 8, 0, 3]

# prints [2, 3]

It does not fulfill your test case 2:

>>> a = [3, 2, 5, 6]
>>> b = [17, 28, 2, 8, 0, 3]
>>> tmp.magic(a,b)
[3]
# you wanted [2]

But it does follow my earlier comment (to which you said "YES")

@jevik So what you want to do is to take a[0] iff it is in b, then take a[1] iff it is in b after the index where a[0] was in b and so on? – lucidbrot 41 mins ago

Your test case 3 from a comment:

For a=7 8 6 6 8 10 3 3 and b=7 4 10 8 7 with your solve I get 7 8 10. I need to get 7 8

My program does print [7,8] for that.

Answer 5

You can use & operation between two sets, that will give you an intersection set without change in order

a = [2, 3, 5, 6]
b = [17, 28, 2, 8, 0, 3]

intersection = list(set(a) & set(b))
print(intersection)