Find the number of pairs in an array while (x,y)==(y,x), and each pair will be counted only once-CodePudding

Find the number of pairs in an array while (x,y)==(y,x), and each pair will be counted only once.

for example, the array [ [1,2], [2,1], [3,1] ] [1,2] and [2,1] will be a pair and output count=1.

And in the array [ [1,2], [2,1], [2,1] ] once [1,2] is paired with the first [2,1], it is not be able to paired with the second[2,1], so it should output count=1

I'm considering once find a pair, then delete the two items in the array, but it doesn't work efficiently. So is there a more efficient way doing this in Python? Thank you

CodePudding user response：

You could use Counter and then take the minimum frequency of a tuple and its inverse. Since this will double count, divide the result by 2:

from collections import Counter

def countpairs(lst):
    ctr = Counter(map(tuple,lst))
    return sum(min(count, ctr[(b, a)]) for (a, b), count in ctr.items()) // 2

Some runs:

print(countpairs([ [1,2], [2,1], [2,1], [1,2], [2,1] ])) # 2
print(countpairs([ [1,2], [2,1], [13,1], [1,2], [2,1] ])) # 2
print(countpairs([ [13,1], [13,1], [1,2]])) # 0

CodePudding user response：

You need to make something unique to identify all combination of pair.

one way is sort the sublist (pair) and then use all the sublist who when sorted map to that unique value.

Below is implementation of that using, dictionary (keys are unique in it)

a = [ [1,2], [2,1], [3,1] ]
dic = {}
for i, j in a:
    if i < j:
            dic[(i, j)] = [i, j]
    else:
            dic[(j, i)] = [j, i]

solution = list(dic.values())
print(solution)
# output [[1, 2], [1, 3]]

CodePudding user response：

The Python standard library has a helpful class, Counter, that as the name suggests counts things. ;^) Sorting each pair of elements in the the input list allows makes them the same for counting purposes. Lastly, summing up the number of pairs that appear more than once will produce the correct output:

from collections import Counter

def count_pairs(arr):
    counter = Counter(tuple(sorted(a)) for a in arr)
    return sum(1 for value in counter.values() if value > 1)

print(count_pairs([[1, 3], [1, 2], [2, 1], [1, 2], [3, 1]]))

Output:

CodePudding user response：

Thanks to set lookups being constant time, here is an efficient implementation of the algorithm that runs in o(n/2). Thanks to @Mark for proposing the idea of using sets.

def get_num_inverted(set_):
    count = 0
    while set_:
        element = set_.pop()
        if element[::-1] in set_:
            set_.remove(element[::-1])
            count  = 1
    return count

Speed:

set_ = set([(random.randint(0, 500), random.randint(0, 500)) for i in range(100_000)])
%timeit get_num_inverted(set_.copy())

output:

28.6 ms ± 1.62 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

For values between 0 and 100, here is how it runs for different sizes: