Общие элементы между двумя списками, не используя наборы в 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 в двух входных списках. Из вашего вопроса неясно, хотите ли вы такого поведения.

SilentGhost, Марк Дикинсон и Лоорис правы, спасибо очень важно, чтобы сообщить об этой проблеме - мне нужна общая часть списков, поэтому для:

a = [1,1,1,2]

b = [1,1,3,3]

результат должен be [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

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