1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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*}

$\endgroup$
  • $\begingroup$ What you are suggesting that I should write the mathematical expression in two phases as you did for first code snippet. However, I need to write the expression for n number of loops, I mean in generalized form. @Code review: For my case, I can not assume that $0\leq i_1, i_2 <N$, they can have different size. $\endgroup$ – Md. Shahriar Mahbub Oct 7 '16 at 9:16
  • $\begingroup$ @Md.ShahriarMahbub: A two step description seems to be convenient. I can add a generalized version if needed. But first of all a question to the distance function. Is it symmetrical, i.e. $d(S_i,S_j)=d(S_j,S_i)$ and $d(S_i,S_i)=0$ for all $i,j$? In that case you should be able to code it as $N:=\max\{N_1,N_2\}$ and iterate in two for-loops according to $0\leq i_2 <i_1<N$. $\endgroup$ – Markus Scheuer Oct 7 '16 at 15:42
  • $\begingroup$ It would be good, if you provide a generalized version. Please consider solutions are taken from different solution set (please see second code snippet). yes it is symmetrical for my case. Iterate in two for-loops according to $0 \leq i_2 < i_1 < N$, is this case, do you consider, $N_1>N2$ ? $\endgroup$ – Md. Shahriar Mahbub Oct 10 '16 at 8:26
  • $\begingroup$ @Md.ShahriarMahbub: I will provide a generalised version after work in the evening. One aspect which could be helpful for your coding. If you have to consider different $N_1,N_2,\ldots,N_k$ and you take pairwise limits in each for-loop, you could implement it as $0\leq i_2<i_1<\max\{N_1,N_2\}; 0\leq i_3<i_2<\max\{N_2,N_3\}; \ldots ;0\leq i_k<i_{k-1}<\max\{N_{k-1},N_k\}$. $\endgroup$ – Markus Scheuer Oct 10 '16 at 9:10
  • $\begingroup$ @Md.ShahriarMahbub: General case added. Regards, $\endgroup$ – Markus Scheuer Oct 10 '16 at 21:08
-1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Many thanks. Can you please help me to interpret the notation you suggest. Are you presenting x as index? Means $dis(S_{x_i}, S_{x_{i+1}})$? With your proposed notation, how can I show indices are the Cartesian product. @LinAlg $\endgroup$ – Md. Shahriar Mahbub Oct 3 '16 at 21:28
  • $\begingroup$ Your $i$ and $j$ are my $x_1$ and $x_2$. For the remainder it's just basic set notation. $\endgroup$ – LinAlg Oct 3 '16 at 21:32
  • $\begingroup$ With your proposed notation, how can I show indices are the Cartesian product. I mean all the combinations. is $x \in \mathbb{R}^n$ means that? So, the equation becomes $\arg\min_{ x \in \mathbb{R}^n} \{ \sum_{i=1}^{n-1} dis(S_{x_i},S_{x_{i+1}}) : x_i < n_i \; i = 1,2,\ldots,n-1 \}$ $\endgroup$ – Md. Shahriar Mahbub Oct 3 '16 at 21:36
  • $\begingroup$ Right! $\mathbb{R}^2 = \mathbb{R}\times\mathbb{R}$. $\endgroup$ – LinAlg Oct 3 '16 at 21:42
  • $\begingroup$ Why not ${ x \in \mathbb{N}^n}$, $\mathbb{N}$ refer to natural number set. $\endgroup$ – Md. Shahriar Mahbub Oct 3 '16 at 21:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.