Общие элементы между двумя списками, не использующие наборы в Python

В Python 3.x (и Python 2.7, когда он будет выпущен) вы можете использовать collections.Counter для этого:

>>> from collections import Counter
>>> list((Counter([2,2,1,1]) & Counter([1,3,3,1])).elements())
[1, 1]

Вот альтернатива с использованием collections.defaultdict (доступно в Python 2.5 и более поздних версиях). . Его приятное свойство состоит в том, что порядок результата является детерминированным (по сути, он соответствует порядку второго списка).

from collections import defaultdict

def list_intersection(list1, list2):
    bag = defaultdict(int)
    for elt in list1:
        bag[elt] += 1

    result = []
    for elt in list2:
        if elt in bag:
            # remove elt from bag, making sure
            # that bag counts are kept positive
            if bag[elt] == 1:
                del bag[elt]
            else:
                bag[elt] -= 1
            result.append(elt)

    return result

Для обоих этих решений количество вхождений любого данного элемента x в выходной список равно минимальному количеству вхождений x в двух входных списках. Из вашего вопроса не ясно, нужно ли вам такое поведение.

Использование наборов является наиболее эффективным, но вы всегда можете сделать r = [i for i in l1 if i in l2].

SilentGhost, Mark Dickinson и Lo'oris правы. Большое спасибо за сообщение об этой проблеме - мне нужна общая часть списков, поэтому для:

a=[1,1,1,2]

b=[1,1,3,3]

результат должен быть [1,1]

Извините за комментарий в неподходящем месте - я зарегистрировался сегодня.

Я изменил ваши решения:

def count_common(l1,l2):
        l2_copy=list(l2)
        counter=0
        for i in l1:
            if i in l2_copy:
                counter+=1
                l2_copy.remove(i)
        return counter

l1=[1,1,1]
l2=[1,2]
print count_common(l1,l2)

1