Как посчитать количество пар в массиве 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]))
→ Ссылка
Автор решения: CrazyElf

Вообще надо проверять только "нижний треугольник" квадрата, но это надо индексы сравнивать, проще посчитать все пары, потом вычесть совпадения чисел самих с собой и поделить на 2, чтобы убрать повторные совпадения с другой стороны диагонали:

lst = [1,2,3,2,3,3]
print((sum(a == b for a in lst for b in lst) - len(lst))//2)
# 4
→ Ссылка
Автор решения: EzikBro
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.

→ Ссылка