Combinations:

In last post I talked about calculating permutation. Combinaitons differ from permutation in that ordering does not matter in case of combinations. For example we were concerned about first digit, second digit etc, whereas in combination it will not matter. For example we need to pull 4 balls out of 10, order does not matter. To make it easy, let us say 2 balls are to be choosen out of 4

So we can choose

1,2
1,3
1,4
2,3
2,4
3,4

Total 6

Whereas when we were talking about permutation, we were concerned about order as well. So 1,2 was different from 2,1

1,2
1,3
1,4
2,1
2,3
2,4
3,1
3,2
3,4
4,1
4,2
4,3
Total 12, same as 4P2 or 4!/(4-2)!

So the difference between permutation and combination is that we have removed ordering info in case of combinations. In how many ways we can order 2 numbers, exactly 2 (1,2 or 2,1). In how many ways we can order 3 objects- 6 (1,2,3; 1,3,2; 2,1,3; 2,3,1; 3,1,2; 3,2,1) or 3!. Similarly we can prove n objects can be ordered n! times.

So a formula for combinations would be nPr/r!

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

Using it for 4 balls out of 10
10!/4!6! = 210

If I go back to my previous post of finding traveling salesman problem, and I need to know how many options are available to visit all the cities, understanding of permutations and combinations can help me.

Permutation: In how many ways we can choose and arrange options. For example, you have to create N digit number as a code, say 4 digit number.

You can choose the number in 10^4 ways. This is how-

First digit- 10 options (0 to 9 – say 0 is allowed)
Second digit- 10 options
and so on.

So at the end we have
10*10*10*10 options or 10^4

or to generalize

n*n*n*n.. r times i.e. n^r

The above case is for permutation where repetition is allowed. There can be a case where repetition is not allowed, e.g. instead of choosing numbers randomly, we are picking random balls from a sack. So if you have picked ball number 7 once, it will not be available for reuse.

First digit- 10 options
Second digit- 9 options (first digit option not available for reuse).
Third- 8
Fourth- 7

Total Options 10*9*8*7

generalize

n*(n-1)*(n-2).. (n-r)

nPr = n!/(n-r)!

Traveling salesman problem is a classic NP hard problem.

Problem Statement: A salesman has to visit N number of cities, say A, B, C and D. He is starting from A, and need to visit all other cities in a way that he has to cover shortest distance.

Solution: Ideal solution will be to figure out all the permutations of traveling N cities, and then choose the one where distance traveled is smallest.

Finding all Permutations is definitely a trouble. 10! will take us into million permutations and moving ahead further adds to trouble.

One solution can be to pick random city from every city and move ahead. A little betterment will be to move to next nearest city instead of random city.

1. Start from city 0
2. Look for the nearest city, not visited already
3. Go to the nearest city, mark it visited
4. If not all city visited, go to 2

Here is a piece of code

public static int travel()
{
currcity=0;
path[index++]=0;

int[][] tempdistance=distance.clone();
printarr(tempdistance);
citiesLeft=removeArr(citiesLeft, currcity);

while(citiesLeft.length>0)
{
int nextcity=findNearest(currcity, tempdistance);
path[index++]=nextcity;
currcity=nextcity;
citiesLeft=removeArr(citiesLeft, currcity);
printarr(tempdistance);
}
//Final path
for(int i=0;i<path.length;i++) System.out.print(path[i]+">");
return -1;
}


Here is the complete code

public class TravelingSalesman {

static int distance[][]={
//AA=0; AB=1; AC=2; AD=3
{0,6,2,1},
{2,0,2,3},
{1,2,0,1},
{6,10,2,0}
};

static int path[]=new int[4];
static int currcity=0;
static int index=0;
static int totalcity=0;
static int[] citiesLeft={0,1,2,3};

public static void main(String sp[])
{
totalcity=distance[0].length;
System.out.println(travel());
}

public static int travel()
{
/*
* 1. Start from city 0
* 2. Look for the nearest city, not visited already
* 3. Go to the nearest city, mark it visited
* 4. If not all city visited, go to 2
*/

currcity=0;
path[index++]=0;

int[][] tempdistance=distance.clone();
printarr(tempdistance);
citiesLeft=removeArr(citiesLeft, currcity);

while(citiesLeft.length>0)
{
int nextcity=findNearest(currcity, tempdistance);
path[index++]=nextcity;
currcity=nextcity;
citiesLeft=removeArr(citiesLeft, currcity);
printarr(tempdistance);
}
//Final path
for(int i=0;i<path.length;i++) System.out.print(path[i]+”>”);
return -1;
}

public static int[] removeArr(int[] arr, int num)
{
int[] citiesLeft=new int[arr.length-1];
if(citiesLeft.length==0)
return citiesLeft;
int j=0;
for(int i=0;i<arr.length;i++)
{
if(arr[i]!=num)
citiesLeft[j++]=arr[i];
}
return citiesLeft;
}

public static boolean availableInCitiesLeft(int check)
{
for(int i=0;i<citiesLeft.length;i++)
{
if(citiesLeft[i]==check)
return true;
}
return false;
}

public static int findNearest(int curr, int arr[][])
{
int nearest=0;
int nearestval=0;
for (int i=0;i<arr[0].length;i++) { if(availableInCitiesLeft(i)) if(arr[curr][i]>0)
if(nearestval<=0 || arr[curr][i]<nearestval)
{
nearestval=arr[curr][i];
nearest=i;

}
}
return nearest;
}

public static void printarr(int arr[][])
{
for(int i=0;i<arr[0].length;i++){
for(int j=0;j<arr[0].length;j++){
System.out.print(arr[i][j]+”,”);
}
System.out.println(“”);
}
System.out.println(“—————————-”);

}

}