Python3 находит, сколько различий в 2 списках, чтобы быть равными

Question

Предполагая, что мы получили 2 списка, всегда с одинаковой длиной и всегда , содержащие строки.

list1 = ['sot', 'sot', 'ts', 'gg', 'gg', 'gg']
list2 = ['gg', 'gg', 'gg', 'gg', 'gg', 'sot']

нам нужно найти:

Сколько пунктов list2 должно измениться, чтобы оно равнялось list1.

Так что в предыдущем примере он должен вернуть 2

Для этого примера:

list1 = ['sot', 'sot', 'ts', 'gg', 'gg', 'gg']
list2 = ['gg', 'gg', 'gg', 'gg', 'sot', 'sot']

он должен вернуть 1

и, наконец,для этого примера:

list1 = ['sot', 'sot', 'ts', 'gg', 'gg', 'gg']
list2 = ['ts', 'ts', 'ts', 'ts', 'ts', 'ts']

должно возвращаться 5.

Нам не важно, какие элементы должны измениться на какие.Мы не заботимся о порядке, поэтому это означает, что

['gg', 'gg', 'gg', 'gg', 'gg', 'sot'] 
and
['gg', 'gg', 'sot', 'gg', 'gg', 'gg']

равны, и результат их должен быть 0.

Длина списков может быть 6, 8, 20 иливсе, что угодно, иногда есть больше элементов.

Я пробовал много вещей, таких как set(list1) - set(list2), list(set(list1).difference(list2)), set(list1).symmetric_difference(set(list2)), но безуспешно.

Answer 1

Вы можете использовать множество возможностей Counter предложений:

list1 = ['sot', 'sot', 'ts', 'gg', 'gg', 'gg']
list2 = ['gg', 'gg', 'gg', 'gg', 'gg', 'sot']

from collections import Counter

sum((Counter(list1) - Counter(list2)).values())
# 2

---

Давайте посмотрим на другие примеры:

list1 = ['sot', 'sot', 'ts', 'gg', 'gg', 'gg']
list2 = ['gg', 'gg', 'gg', 'gg', 'sot', 'sot']

sum((Counter(list1) - Counter(list2)).values())
# 1

list1 = ['sot', 'sot', 'ts', 'gg', 'gg', 'gg']
list2 = ['ts', 'ts', 'ts', 'ts', 'ts', 'ts']

sum((Counter(list1) - Counter(list2)).values())
# 5

list1 = ['gg', 'gg', 'gg', 'gg', 'gg', 'sot'] 
list2 = ['gg', 'gg', 'sot', 'gg', 'gg', 'gg']

sum((Counter(list1) - Counter(list2)).values())
# 0

---

Подробности

Используя Counter, вы получите счетчик всех элементов из каждого списка в виде словаря. Вернемся к первому примеру:

c1 = Counter(list1)
# Counter({'sot': 2, 'ts': 1, 'gg': 3})

c2 = Counter(list2)
# Counter({'gg': 5, 'sot': 1})

Теперь мы как-то хотели бы понять:

• Какие элементы присутствуют в list1, но отсутствуют в list2

• Из тех, кто присутствует, а также тех, которых нет, сколько еще нужно в list2, чтобы они содержали одинаковое количество импульсов

Хорошо, мы могли бы воспользоваться тем фактом, что счетчики поддерживают математические операции, в результате которых создаются multisets, то есть счетчики, у которых счетчики больше нуля. Поэтому, учитывая, что мы ищем разницу между обоими счетчиками, кажется, что мы могли бы вычесть их и посмотреть, какие элементы и их соответствующие значения необходимы в list2.

Так как же будет работать вычитание между счетчиками? Давайте проверим простой пример:

Counter({1:4, 2: 1}) - Counter({1:1, 3:1})  
# Counter({1: 3, 2: 1})

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

 sub = Counter(list1) - Counter(list2)
# Counter({'sot': 1, 'ts': 1})

Теперь нам просто нужно посчитать values во всех keys, что можно сделать с помощью:

sum(sub.values())
# 2

Answer 2

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

Стандартная библиотека Python имеет многосетевую реализацию: collections.Counter(), которая отображает уникальные элементы на счет. Используйте их здесь:

from collections import Counter

mset1 = Counter(list1)
mset2 = Counter(list2)

# sum the total number of elements that are different between
# the two multisets
sum((mset1 - mset2).values())

Вычитание одного счетчика из другого дает вам мультимножество всех элементов, которые были в первом мультимножестве, но не в другом, и sum(mset.values()) складывается из общего количества элементов.

Поскольку входные данные всегда имеют одинаковую длину, и вам нужно только знать, сколько элементов различается, не имеет значения , в каком порядке вычитать мультимножества. Вы всегда получите правильный ответ, и sum((mset1 - mset2).values()) и sum((mset2 - mset1).values()) всегда будут давать одно и то же число.

Это потому, что оба мультимножества имеют N элементов, из которых K разные. Таким образом, оба мультимножества будут иметь ровно K дополнительных элементов, которых нет в другом мультимножестве, и иметь K , пропущенных элементов, которые присутствуют в другом наборе. - вычитание даст вам K дополнительных элементов в первом наборе, которые отсутствуют в другом.

Помещаем это в функцию:

def mset_diff(iterable1, iterable2):
    return sum((Counter(iterable1) - Counter(iterable2)).values())

и применяется к вашим входам:

>>> mset_diff(['sot', 'sot', 'ts', 'gg', 'gg', 'gg'], ['gg', 'gg', 'gg', 'gg', 'gg', 'sot'])
2
>>> mset_diff(['sot', 'sot', 'ts', 'gg', 'gg', 'gg'], ['gg', 'gg', 'gg', 'gg', 'sot', 'sot'])
1
>>> mset_diff(['sot', 'sot', 'ts', 'gg', 'gg', 'gg'], ['ts', 'ts', 'ts', 'ts', 'ts', 'ts'])
5

Класс Counter() является подклассом dict, подсчет элементов быстрый и эффективный, а вычисление разницы между ними выполняется за O (N) линейное время.

Answer 3

Использование set вызовет проблемы, если разница в , сколько присутствует определенного элемента.Вместо этого используйте collections.Counter.Как объясняется в других ответах, вы можете создать Counter для обоих списков, а затем использовать -, чтобы получить разницу между ними и получить sum из values.Однако обратите внимание, что это будет только , если списки имеют одинаковый размер .Если списки не имеют одинаковое количество элементов, вы получите различное количество расходящихся элементов в зависимости от того, из какого списка вычтен какой из них.

С subtract, с другой стороны, вы получитеразница в в обоих направлениях с использованием положительных чисел для элементов, которые "слишком много", отрицательны для "слишком мало".Это означает, что вам, возможно, придется разделить результат на 2, то есть sum(...) / 2, но это должно работать лучше для списков разного размера.

>>> list1 = ['sot', 'sot', 'ts', 'gg', 'gg', 'gg']
>>> list2 = ['gg', 'gg', 'gg', 'gg', 'sot', 'sot']
>>> c = Counter(list1)
>>> c.subtract(Counter(list2))
# Counter({'gg': -1, 'sot': 0, 'ts': 1})
>>> sum(map(abs, c.values()))
2

Другая возможность, которая также надежно работает со списками разного размера, использует & для получения общих элементов и их сравнения с общим количеством элементов в больше список:

>>> list1 = [1,1,1,1,2]
>>> list2 = [2]
>>> Counter(list1) & Counter(list2)
Counter({2: 1})
>>> max(len(list1), len(list2)) - sum((Counter(list1) & Counter(list2)).values())
4

Answer 4

Для этого вы можете использовать collections.Counter, где вы подсчитываете, сколько предметов есть в обоих списках, и берете разницу между ними.

from collections import Counter
def func(list1, list2):
    #Convert both list to counters, and subtract them
    c = Counter(list1) - Counter(list2)

    #Sum up all values in the new counter
    return sum(c.values())

Выходы

list1 = ['sot', 'sot', 'ts', 'gg', 'gg', 'gg']
list2 = ['gg', 'gg', 'gg', 'gg', 'gg', 'sot']
print(func(list1, list2))
#2

list1 = ['sot', 'sot', 'ts', 'gg', 'gg', 'gg']
list2 = ['gg', 'gg', 'gg', 'gg', 'sot', 'sot']
print(func(list1, list2))
#1

list1 = ['sot', 'sot', 'ts', 'gg', 'gg', 'gg']
list2 = ['ts', 'ts', 'ts', 'ts', 'ts', 'ts']
print(func(list1, list2))
#5