How can I create a fomula to calculate iterations between 2 numbers where on keep reducing at each iteration?

Question

I am a software Engineer and I've run into an issue and I need to generate a kind of formula that will help me calculate iterations.

I thought of asking this question on stackoverflow but what I need here is a formula that can help me.

Note: I am really interested in understanding the process of forming a formula like this. If you can, please refer me to a math topic online that I can study to help me generate a formula like this myself next time.

Here is the Basics

• The codes work really well right now so all I need know is a formula. (maybe something like series or permutation ).
• I am building an API that can take two zip codes, and then find the distance between them.
• It works great using Google's geocoding APIs but now I want to build a data warehouse myself, cache it how I want and then be able to provide some services with it.
• The idea is to expose some endpoints that can be hit with two zip codes and then the distance between them returned (ignoring the road paths which was an advantage I get with the google API).
• Am building the API with nodejs and I use the haversine formula for the calculation.
• Currently running the code on my Linux machine while storing the data in MYSQL database.
• Later, I will running the code as AWS Lamda function while saving the data in RDS Mysql.

The Problem.

• The problem is, the number of iteration I run to calculate the distance between each zip code increases as the number of zip codes increases.

• Note: I'll run this just ones (to generate the distances) and then for subsequent new zip codes that might be added in the future, the iterations will be minimal.

• Say you have 4 zip codes,

• Then you calculate the distance between

  • 1 and 2, 1 and 3, 1 and 4,
  • 2 and 3, 2 and 4
  • 3 and 4

• So this will require 6 iterations.

However, say you have 10 zip codes, then you will calculate distances between

• 1 and 2, 1 and 3, 1 and 4, 1 and 5, 1 and 6, 1 and 7, 1 and 8, 1 and 9, 1 and 10,
• 2 and 3, 2 and 4, 2 and 5, 2 and 6, 2 and 7, 2 and 8, 2 and 9, 2 and 10,
• 3 and 4, 3 and 5, 3 and 6, 3 and 7, 3 and 8, 3 and 9, 3 and 10,
• 4 and 5, 4 and 6, 4 and 7, 4 and 8, 4 and 9, 4 and 10,
• 5 and 6, 5 and 7, 5 and 8, 5 and 9, 5 and 10,
• 6 and 7, 6 and 8, 6 and 9, 6 and 10,
• 7 and 8, 7 and 9, 7 and 10,
• 8 and 9, 8 and 10,
• 9 and 10, And that will be about 45 iterations, up from 6 iterations when we had 4 zip codes.

How can I form a formula to calculate this by just plugin in some values and do the calculations.

Currently I have a typescript method that does the calculation but it has to loop through continuously.

  private calculateIterations(start: number = 1, total: number = 300) {
    // Holds the number of iterations.
    let count = 0;
    // Loop through {total} times.
    for (let a = 0; a < total; a++) {
      // For each item, loop through the rest of the items.
      for (let b = (a + 1); b < total; b++) {
        // Increment the count for each sub iteration.
        count++;
        console.log('count = ', count, ' | a = ', a, ' b = ', b);
      }
    }
  }
  

Answer 1

So I did more research and found out that this is related to permutations and combinations.

Permutation where order matters, and combination, where order doesn't matter. Watching these videos https://youtu.be/gAnKvHmrJ0g and https://youtu.be/tnF9f3zCCKI gave me more ideas. This also helped a lot.

In my case, its actually a combination (since my goal is to pair 2 coordinates at once while ignoring their order) and so using the formula nCr = n! / (n-r)! r! where n = total_number_of_items and r = number_of_items_picked_at_once.

Note that n! means n factorial so if n = 4, n! will be equal to 4! and that will equals 4 * 3 * 2 * 1 = 24.

So say I have 4 items, and I pick a combination of 2 at once, then we can work it out as

nCr = n! / ( r!(n-r)! )

= 4! / ( r!(4 - 2)! )

= (4 * 3 * 2 * 1) / ( 2!(2!) )

= 24 / ( 2(2) )

= 24 / ( 4 )

= 6

Since I needed to find the distance between 2 coordinates at a time, I am able to calculate how many iterations I'll need to make using this formula.

Answer 2

It sounds like you have $n$ zip codes and that you need an iteration for every pair of zip codes. The number of such pairs is $n(n-1)/2$.

Answer 3

Make a square with the entries at the row- and the column-indexes being the zip codes. And in the entries in the square-matrix itself the distances.Example with 4 zipcodes $$ \begin{array} {r|rrrr|} * & c_1 & c_2 & c_3 & c_4 \\ \hline c_1 &d_{11} & d_{12}& d_{13}& d_{14} \\ c_2 &d_{21} & d_{22}& d_{23}& d_{24} \\ c_3 &d_{31} & d_{32}& d_{33}& d_{34} \\ c_4 &d_{41} & d_{42}& d_{43}& d_{44} \\ \end{array} $$ Here all diagonal entries are zero, so remove that entries from the matrix. you have $4 \cdot 4 - 4 =4 \cdot(4-1) $ entries remaining.
After that notice that all entries are equal whose indexes are mirrored, so $d_{12}=d_{21}$ So the final number is the previous result divided by $2$. $$4 \cdot (4-1) \over 2$$ and in general $$ {n \cdot (n-1)\over 2}$$ The latter can be expanded on numerator and denominator th see the basic definition of the binomial: $$ { n (n-1) \cdot \color{red}{(n-2)(n-3)...(1)} \over 2 \cdot \color{red}{(n-2)(n-3)...(1)} } = { n!\over 2! (n-2)! } $$

---

Unfortunately, if you want to see this for higher binomials you need 3-dimensional or more dimensional arrays to show this...