How to write n number of loops mathematically

Question

I have the following code. I want to write it mathematically. Any help would be appreciated.

int in1=1, in2=-1;
double totalDistance=0.0;
double min_dis = Double.MAX_VALUE;
for(int i=0;i<N1;i++){
    for(int j=0;j<N2;j++){
        dis = calculateDistance(Solutions(i),Solutions(j));
                totalDistance = dis;
                if(totalDistance< min_dis){
                    min_dis=totalDistance;
                    in1=i;
                    in2=j;
            }   
        }
    }
print(in1, in2)

Mathematically, I write it as follows: \begin{equation} argmin_{i,j \in \{1,2, \dots, n_1\} \times \{1,2, \dots, n_2\}} dis(S_i, S_j) \end{equation} $\times$ refers to Cartesian product between sets and ${dis(S_i, S_j)}$ is the distance.

I want to know is it correct mathematical representation. If it is correct, I want to extend it to n loops. Following is an example of 3 loops.

int in1=1, in2=-1, in3=-1;
    double totalDistance=0.0;
    double min_dis = Double.MAX_VALUE;
    for(int i=0;i<N1;i++){
        for(int j=0;j<N2;j++){
            double dis1 = calculateDistance(**S1**(i), **S2**(j));
            for(int z=0;z<N3;z++){
                double dis2 = calculateDistance(**S2**(j), **S3**(z));
                totalDistance = dis1+ dis2;
                if(totalDistance< min_dis){
                    min_dis=totalDistance;
                    in1=i;
                    in2=j;
                    in3=z;
                }
            }
        }
    }
    print(in1 in2 in3);

How can I represent the generalized version in mathematical notation?

Thanks in advance.

Answer 1

Define the set of minimizers:

$S = \arg\min_{ x \in \mathbb{N}^n} \{ \sum_{i=0}^{n-2} dis(S_{x_i},S_{x_{i+1}}) : x_i < n_i \; i = 0,1,\ldots,n-2 \}$

The solution is the lexicographic first element of $S$:

$\min\{x \in S \}$

where $\min$ performs lexicographic minimization. This returns the same element of $S$ that your code outputs.

Answer 2

The mathematical expression is not correct. Here we focus on the first code snippet. The consideration for the second part and the general case is similarly.

Some aspects need to be considered in more detail:

• There may be more than one pair with minimum distance, while the code returns always a single element.

• The order of the for-loops: This is important in case there are more than one element with minimum distance.

• Technical detail: The index range is $0\leq i < N$ instead of $1\leq i\leq N$.

In the following we use the notation \begin{align*} \operatorname{calculateDistance(Solutions(i),Solutions(j))}\quad&\longrightarrow\quad d(S_i,S_j)\\ \operatorname{N1}\quad&\longrightarrow\quad N_1\\ \operatorname{N2}\quad&\longrightarrow\quad N_2\\ \operatorname{in1}\quad&\longrightarrow\quad i_1\\ \operatorname{in2}\quad&\longrightarrow\quad i_2\\ \end{align*}

First step: $2$ loops

Let $N_1,N_2>0$. We obtain, assuming symmetry of the distance function

\begin{align*} A_2&:={\operatorname{argmin}}_{0\leq i_2<i_1<\max\{N_{i_1},N_{i_{2}}\}}\{d(S_{i_1},S_{i_2})\}\\ &=\{(i_1,i_2):d(S_{i_1},S_{i_2})\leq d(S_{j_1},S_{j_2}),0\leq i_1,j_1<N_1, 0\leq i_2,j_2<N_2\}\\ \\ B_2&:=\min_{0\leq i_2<N_2}\min_{0\leq i_1<N_1}\{(i_1,i_2):(i_1,i_2)\in A_2\} \end{align*} with $B_2$ consisting of the one element which is returned by the code.

There may be more than one pair with the same minimum distance, so that $A_2$ will contain usually more than one element. Assume the set $A_2$ contains the four elements \begin{align*} A_2=\{(4,3),(4,5),(8,2),(10,6)\} \end{align*} In this case the code will return $(4,3)$. Since $4$ is the smallest value of the first coordinates, the candidates from $A_2$ are $(4,3)$ and $(4,5)$. Out of these two values the code selects the one with the lowest second coordinate giving $(4,3)$.

This implies that the order of the minimum settings in $B_2$ is essential. Note that \begin{align*} B_2=&\min_{0\leq k_2<N_2}\min_{0\leq k_1<N_1}\{(k_1,k_2):(k_1,k_2)\in A_2\}=\{(4,3)\}\quad\text{while}\\ &\min_{0\leq k_1<N_1}\min_{0\leq k_2<N_2}\{(k_1,k_2):(k_1,k_2)\in A_2\}=\{(8,2)\}\\ \end{align*}

General step: $k$ loops

Let $N_1,N_2,\ldots,N_k>0,k\geq 2$. We obtain

\begin{align*} A_k&:={\displaystyle{{\text{argmin}}_{{0\leq i_l<i_{l+1}<\max\{N_{i_l},N_{i_{l+1}}\}}\atop{1\leq l\leq k-1}}} \left\{\sum_{j=1}^{k-1}d(S_{i_j},S_{i_{j+1}})\right\}}\\ \\ B_k&:=\min_{0\leq i_k<N_k}\min_{0\leq i_{k-1}<N_{k-1}} \cdots\min_{0\leq i_1<N_1}\{(i_1,i_2,\ldots,i_k):(i_1,i_2,\ldots,i_k)\in A_k\} \end{align*} with $B_k$ consisting of the one element which is returned by the code.

Code review:

• $\operatorname{in1}$ should be initialised with $-1$

• Since both indices $i$ an $j$ are the argument for the call $\operatorname{calculateDistance(S(i),S(j))}$ and the call is symmetrical with respect to the arguments it is not sound, that $i$ and $j$ have different range. We would rather assume \begin{align*} &0\leq i_1,i_2< N_1\\ \end{align*}

• We expect a distance function $d$ to act symmetrically: $d(x,y)=d(y,x)$ for all $x,y$ and also $d(x,x)=0$ for all $x$. So, we would rather code \begin{align*} &0\leq i_2 < i_1<N_1\\ \end{align*}