How do I get the total number of unique pairs of a set in the database? [closed]
4 items:
A
B
C
D
6 unique pairs possible:
AB
AC
AD
BC
BD
CD
What if I have 100 starting items? How many unique pairs are there? Is there a formula I can throw this into?
TLDR; The formula is n(n-1)/2 where n is the number of items in the set.
Explanation:
To find the number of unique pairs in a set, where the pairs are subject to the commutative property (AB = BA), you can calculate the summation of 1 + 2 + ... + (n-1) where n is the number of items in the set.
The reasoning is as follows, say you have 4 items:
A
B
C
D
The number of items that can be paired with A is 3, or n-1:
AB
AC
AD
It follows that the number of items that can be paired with B is n-2 (because B has already been paired with A):
BC
BD
and so on...
(n-1) + (n-2) + ... + (n-(n-1))
which is the same as
1 + 2 + ... + (n-1)
or
n(n-1)/2
What you're looking for is n choose k. Basically:
For every pair of 100 items, you'd have 4,950 combinations - provided order doesn't matter (AB and BA are considered a single combination) and you don't want to repeat (AA is not a valid pair).
This is how you can approach these problems in general on your own:
The first of the pair can be picked in N (=100) ways. You don't want to pick this item again, so the second of the pair can be picked in N-1 (=99) ways. In total you can pick 2 items out of N in N(N-1) (= 100*99=9900) different ways.
But hold on, this way you count also different orderings: AB and BA are both counted. Since every pair is counted twice you have to divide N(N-1) by two (the number of ways that you can order a list of two items). The number of subsets of two that you can make with a set of N is then N(N-1)/2 (= 9900/2 = 4950).
I was solving this algorithm and get stuck with the pairs part.
This explanation help me a lot https://betterexplained.com/articles/techniques-for-adding-the-numbers-1-to-100/
So to calculate the sum of series of numbers:
n(n+1)/2
But you need to calculate this
1 + 2 + ... + (n-1)
So in order to get this you can use
n(n+1)/2 - n
that is equal to
n(n-1)/2