[database] How do I get the total number of unique pairs of a set in the database?

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?

This question is related to database math

The answer is


What you're looking for is n choose k. Basically:

enter image description here

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).


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

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