Python: count number of pairs in array(list)

Question

A solution for a small algorithmic problem. I believe tests are pretty descriptive:

def pairs(n):
 return n * (n - 1) / 2
def solution(lst): 
 res = 0
 stack = lst[0:1]
 lst = sorted(lst[1:])
 while(len(lst)):
 nxt = lst.pop()
 if len(stack) and stack[0] == nxt:
 stack.append(nxt)
 else:
 res += pairs(len(stack))
 stack = [nxt]
 else:
 res += pairs(len(stack))
 return res
assert(pairs(3) == 3)
assert(pairs(2) == 1)
assert(pairs(0) == 0)
assert(solution([5, 3, 1, 5, 5, 3]) == 4)
assert(solution([5, 5]) == 1)
assert(solution([5]) == 0)
assert(solution([]) == 0)

UPDATE: there is a bug. I shouldn't take a first element before sorting an array

• Graipher: Please add at least a short description of what this code accomplishes. What kind of pairs are you counting?
• kharandziuk: @Trevor next and list are reserved in python. I can reassign them, but it can lead to some errors
• m0etaz: it's a convention to use one trailing underscore to bypass reserved keywords. i.e. next_

Answer 1

From what I see you are counting all the pairs of equal numbers that can be formed. (If not, please clarify)

It can be done in another way:

1. Take the first element of the array.
2. Count the number of elements equal to it in the array. It can be done via filter, storing the result as a new array, then len.
3. Call pairs over the length of the filtered array of step 2.
4. Add the result of pairs to an accumulator (previously initalized at 0).
5. Repeat steps 2--5 from the next element that is not equal to the one taken previously (for the first iteration, it would be the one taken in step 1). This can be done using filter, then assignment over the original array (if you don't want to preserve it).

The accumulator will be the result.

Quickly tested code snippet:

def countPairs(nums):
 count = 0
 while len(nums):
 probe = nums[0]
 count += pairs(len([x for x in nums if x == probe]))
 nums = [x for x in nums if x != probe]
 return count

EDIT.

Filtering can be thought of as an O(n) operation (iterating and adding elements that fulfill the condition). This is done twice inside the loop. Here, n = len(nums).

On the other hand, the external loop will run as many times as unique(nums), where unique is a function that retrieves the number of unique elements inside the array. Why unique? Because on each iteration, all the elements equal to the probe are taken out of the array (including the probe). They can be 1, 3, all of them. This is done for each iteration.

Nevertheless, unique(nums) <= len(nums), so it can be said the external loop will be a O(n) operation in the worst case.

Therefore, my proposed algorithm runs in O(n^2) time, due to traversing the whole array at most as many times as elements would be in the array.

• kharandziuk: complexity of your solutions is O(n!). is it?
• Aura Lesse Programmer: @kharandziuk I've edited my answer to explain the time complexity. It seems yours would be O(n log n), for the sorting done before the loop.
• kharandziuk: yeah, I expect n log n. But, yeap looks like yours is faster. Thx
• kharandziuk: I have another solution below. Can you check it?

Answer 2

Probably, a little bit better solution. Expect O(n) complexity

def pairs(n):
 return n * (n - 1) / 2
def solution(lst):·
 counts = {}
 result = 0
 for e in lst:
 counts[e] = counts.get(e, 0) + 1
 for entry, count in counts.items():
 result += pairs(count)
 return result
assert(pairs(3) == 3)
assert(pairs(2) == 1)
assert(pairs(0) == 0)
assert(solution([5, 3, 1, 5, 5, 3]) == 4)
assert(solution([5, 5]) == 1)
assert(solution([5]) == 0)
assert(solution([]) == 0)

• Aura Lesse Programmer: Using a dictionary to keep the count seems better to me. O(n) overall (including counts.items() as it's being iterated over). Well done!