Найти размер пересечения между двумя списками

Question

Я пытаюсь написать функцию, которая возвращает количество общих элементов между двумя списками. Если элемент встречается j раз в L1 и k раз в L2, то минимум j и k элементов являются общими.

Примеры:

L1 = [1, 2, 3, 4, 5]
L2 = [4, 2]
L3 = [1, 2, 3, 4, 4, 5, 5]
intersection_size ( L1 , L2 ) => 2
intersection_size ( L1 , L3 ) => 5

Я думал отсортировать L1 и L2 в порядке возрастания, а затем сравнить каждый элемент:

def intersection(L1, L2):
    dL1 = L1[:]
    dL2 = L2[:]
    dL1.sort()
    dL2.sort()
    if dL1[1:] == [] or dL2[1:] == []:
        return 0
    if dL1[0] == dL2[0]:
        return 1 + intersection(dL1[1:], dL2[1:])
    elif dL1[0] > dL2[0]:
        return 0 + intersection(dL1, dL2[1:])
    elif dL1[0] < dL2[0]:
        return 0 + intersection(dL1[1:], dL2)

Однако, когда я test intersection([1, 6, 1, 4], [1, 2, 3, 4]), функция дает мне 1 вместо 2. Может кто-нибудь сказать, какая часть неверна?

Я создал dL1 и dL2, поскольку я хочу L1 и L2 для оставайтесь такими же для других целей, и, поскольку я новичок, мне разрешено использовать только базовые c функции рекурсии и абстрактного списка для этого.

Answer 1

Эта часть логически неверна:

    if dL1[1:] == [] or dL2[1:] == []:
        return 0

Базовый случай должен быть, когда один или оба списка пусты. Но вы возвращаете 0, когда один или оба списка имеют один элемент. Это неверно, потому что этот элемент все еще может быть совпадением, поэтому размер пересечения не будет равен 0. Если вы измените это условие на dL1 == [] or dL2 == [], тогда оно будет работать:

>>> intersection(L1, L2)
2
>>> intersection(L1, L3)
5
>>> intersection([1, 6, 1, 4], [1, 2, 3, 4])
2
>>> intersection([1, 1, 1, 2, 2], [1, 1, 2, 2, 2])
4

Answer 2

Будет работать следующее

len(set(L1) & set(L3))

Если вы не хотите использовать sets, вы можете сделать следующее:

def intersection(L1, L2):
    return len([x for x in L1 if x in L2])