Как посчитать количество пар в массиве python?
Как правильнее всего сделать подсчёт количества пар в массиве, например
d = [1,2,3,2,3,3]
Тут имеется три пары и одно уникальное число, какой алгоритм перебора и подсчета будет правильнее всего?
Ответы (3 шт):
Алгоритм далеко не оптимален, но на небольших массивах будет работать чудесно.
def count_pairs(l):
pairs = []
for i, el in enumerate(l):
for i2, el2 in enumerate(l):
if el == el2 and i != i2:
if (i, i2) not in pairs and (i2, i) not in pairs:
pairs += [(i, i2)]
return len(pairs)
print(count_pairs([1,2,3,2,3,3]))
Вообще надо проверять только "нижний треугольник" квадрата, но это надо индексы сравнивать, проще посчитать все пары, потом вычесть совпадения чисел самих с собой и поделить на 2, чтобы убрать повторные совпадения с другой стороны диагонали:
lst = [1,2,3,2,3,3]
print((sum(a == b for a in lst for b in lst) - len(lst))//2)
# 4
from collections import Counter
d = [1,2,3,2,3,3]
counter = Counter(d)
res = sum(v * (v - 1) // 2 for v in counter.values())
print(res) # 4
Или
d = [1,2,3,2,3,3]
d.sort()
res = 0
s = 1
for i in range(1, len(d)):
if d[i] == d[i - 1]:
s += 1
else:
res += s * (s - 1) // 2
s = 1
res += s * (s - 1) // 2
print(res) # 4
Оба алгоритма подсчитывают, сколько раз в массиве встречается каждое уникальное число: в данном случае - {3: 3, 2: 2, 1: 1}. После чего количество пар считается как количество сочетаний по два из n для каждого уникального числа. То есть количество пар троек в данном случае равно 3 * 2 / 2 = 3.