Category Archives: Algorithms

Understanding Permutation and Combination -2

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

Understanding Permutation and Combination -1

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

Solving the Traveling salesman problem

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(“—————————-”);

}

}

Reverse a Link List

private static Node reverseList(Node head){
Node temp=null;
Node temp2=null;
//Initial state- set temp pointer at head->next
if(head.next!=null)temp=head.next;
//Set head.next null as this will eventually become last node
head.next=null;
while(temp!=null)
{
//Temporary pointer 2 to be placeholder of temp.next
temp2=temp.next;
temp.next=head;
head=temp;
temp=temp2;
}
return head;
}

Find Unique Rank for a String

Problem Statement: For each String we need to assign a unique rank.

B will Have higher rank than A
Z Will have higher rank than B
Z will have higher rank than AA
KAMAL will be higher than AMIT (K>A)
KAWAL will be higher than KAMAL (W>A)
and so on

Solution: Assign a numeric value to each character in string and then add them in a way to create a rank.
Value assigned to characters (A is lowest)
A=0.01, b=0.02.. and so on

Algorithm:

1. Loop The characters in string
1a. Assign Face weight to current character (A= 0.01, B= 0.02 etc)
1b. Assign Position Weight to current character (first char is multiple of 0.01, second of 0.0001 and so on)
1c. update totalweight by adding character weight calculated in 1a and 1b
2. Return totalweight

Code:
public static double getRank(String str)
{
str=str.toUpperCase();
char arr[]=str.toCharArray();
double rank=0;
double multiplier= 0.01;
for(int i=0;iAlgorithm Complexity:
Though if you look closely it might give impression of O(N) complexity, where N is characters in destination string. But as if are dealing with controlled input and string can be of average length 6-10 characters, we can easily confirm the algo to be of constant complexity.

Maximum Subarray Problem- N log N solution

For algorithm and explanation, read here.

Code implementation


public class MaxSumTest
{
/**
* Main method
* @param s
*/
public static void main(String s[])
{
int[] arr=new int[10];
arr=new int[]{10, -19 , 8 , 4, -5, 2, -1, 3, 8,-9};

int arrlength=arr.length/2;
int[] arr1=createarr(0,arrlength,arr);
int[] arr2=createarr(arrlength, arr.length,arr);
int sum=maxsum(arr1,arr2);
System.out.println(sum);
}

/**
* To find out maximum sum subarray, following divide and conquer technique is used
* 1. Divide the array in 2 equal parts, now there are 3 possibilities.
* a. Max sum subarray crosses the mid of original array, i.e. a part of solution is in left array and other in right. Finding this is simple as we just need to move backword on left subarray to find the maximum sum, and then move fwd on right array to find max, and finally add the two
* b. The other possibility is that max subarray is completely on left array. This means left subarray becomes main array and we discard right array. We will repeat the steps from 1.
* c. The last possibility is that max subarray is completely on right array. This means right subarray becomes main array and we discard left array. We will repeat the steps from 1.
*/
public static int maxsum(int[] arr1, int[] arr2)
{
int sum1=0;
int maxsum1=0;
int sum2=0;
int maxsum2=0;
int maxsum=0;

//1.a. Find maximum sum crossing the the mid of original array.
for(int i=arr1.length-1;i>=0;i–)
{
sum1=sum1+arr1[i];
if(maxsum1y)
if(x>z)
return x;
else
return z;
else
if(y>z)
return y;
else
return z;
}

/**
* Create a subarray from start to end
* @param start
* @param end
* @param arr
* @return
*/
public static int[] createarr(int start, int end, int[] arr)
{
int[] myarr=new int[end-start];
for(int i=start,j=0;i
Finish.

Revisiting Max Subarray Problem

Sometime back I discussed and solved a problem to find out a subarray from an array which has the maximum sum- here.

I solved the problem using brute force, that is, all the sub arrays were actually created and maximum sum subarray was found. That solution was created in order of N^2 complexity.

Let’s see how can we improve on our solution using divide and conquer approach.

Array: {-1,2,4,60,1,3,-2,-6,7,-9}

If we divide the original array into two half arrays from mid of the array. one of the following must be true

1. Max Subarray is part of first half {-1,2,4,60,1}

2. Max Sub array is part of second half {3,2,-6,7,-9}

3. Max Subarray passes through the mid of array

Array with maximum sum and passes through mid can be easily figured out in order of N. In this we will simply keep moving left and right from the mid until we hit maximum sum array, so first subarray would be 2+4+60+1+3=70

To solve 1 and 2 we will recursively use the approach with the 2 sub arrays (Repeatedly divide the array and find max having mid of the array).

The problem set is getting reduced to half with every iteration, so Log N iterations will be there in total. At max N elements are added (compared to be -ve), in each iteration, hence the total complexity of the algorithm is (N log N), so we are able to reduce the complexity from N^2 to (N log N) with the help of divide and conquer approach.

Merge Sort: Divide and Conquer Approach

Merge sort is classic example of divide and conquer algorithm approach.

Divide and Conquer Algorithm Design approach: The idea is simple, as the term suggest, we try to divide the original problem into multiple smaller problems. These small problems are solved and the solutions then are merged into one final solution.

The concept is used in merge sorting. Input to any sorting algorithm is a random list (array). For sake of this example let’s take a random array of numbers as input.

Divide Phase: Divide the main array into smaller arrays upto a level that it can sorted easily.

Conquer: Merge these entire sorted arrays into the final solution array.

Example – Lets say we have an array

Original: 99, 23, 45, 12, 67, 28, 09, 98, 44, 84

Divide Phase

Arr1: 99, 23, 45, 12, 67                | Arr2:   28, 09, 98, 44, 84

99, 23, 45                    | 12, 67        |28, 09, 98              | 44, 84

99, 23        | 45           |12    | 67     |28, 09        | 98      |44     | 84

99   | 23   | 45           |12    | 67       |28    | 09   | 98      |44     | 84

Merge Phase

23, 99      | 45           |12, 67            |09, 28   | 98           | 44, 84

23, 45, 99                  | 12, 67          | 09, 28, 98              |   44, 84

12, 23, 45, 67, 99                            | 09, 28, 44, 84, 98

09, 12, 23, 28, 44, 45, 67, 84, 98, 99

Complexity Analysis

The Divide phase of merge sort will need log N operations as in every step we are reducing length of array by half.

Merge step will again have log N merges and in each merge step we will have maximum N comparison, so the overall complexity will (N log N)

Quick Sort: Algorithm and Complexity

After talking about Insertion sort and Heap sort, another important sorting algorithm is quick sort. It is pretty simple algorithm, and will be easy to understand using an example. Lets say we have this random array which we are trying to sort

9, 5, 7, 1, 2, 4, 3, 8, 6

Most critical step of quick sort is to select a pivot element from the array. There are multiple approaches to select the pivot like- first element, last element, mid element, random element, mean, median etc. For sake of simplicity, lets say we randomly select the pivot as 5 for first iteration. Once pivot is selected, the array is divided into 2 arrays, one with elements smaller than pivot and other greater

Iteration 1:

A1: 1, 2, 4, 3

P: 5

A2: 9, 7, 8, 6

In next iteration, one of the arrays (A1) is chosen and again a pivot (say 3) is selected. The same exercise is repeated of breaking down the array into 2 sub arrays unless we get an array of size 1. After that the arrays are merged recursively in same order as they were created, ending up into final sorted array.

Average & Best Case: If we take above case where we kept on dividing the problem array into half (N/2 then N/4, N/8 and so on), and hence halfing number of comparison in every next step. we are looking at a complexity of N Log N.

Worst Case: In worst case, lets say we select highest element every time. So instead of having half the elements in an array, we have N-1 elements in next step. So in this case we end up N*N (N Square) complexity

Heapsort: Algorithm and Complexity

Heap sort is one of the most important and interesting algorithms. The implementation is base of many other sophisticated algorithms. We will focus on basics of heap sorting here. Infact, if you understand what a heap data structure is, heap sort is just application of some known simple operations on the heap.

Let’s relook at our heap

heapsort

This is a max heap so let’s try to create an array in reverse sorted order (a min heap is good for sorted in lowest to highest format and vice versa).  Before moving forward, revisit the heap data structure and understand Insert and Delete operations, after that heap sort algorithm is a cake walk.

We know that max heap has a property that element at the top is highest. Using this property, we can create an algorithm like

  1. Create max heap from the random array
  2. Remove top element from heap and add to reverse sorted array
  3. Heapify (restore heap property) the remaining heap elements
  4. Repeat Step 2 till the heap is empty

Step 1 is nothing but inserting all elements of an array to heap. One Insert Key operation takes Log N operations so N elements will take N Log N

Step 2 is order of 1 as we are just removing the top element and adding to our array

Step 3 is nothing but Delete Node operation in heap, i.e.  take last leaf node and add as root, then compare with its child nodes and swap with largest. Repeat the process till heap property is maintained, i.e. child is greater than parent.  This is Log N operations for one heapify.

Step 4 is combination of 2 & 3, N times. Step 2 is constant order and hence can be ignored. This means we have N Step 3 order or N Log N.

Combining Step 1 and 4, we figure out order of heap sort complexity is of  N Log N order.

Related: http://kamalmeet.com/2013/05/heap-data-structure/

http://kamalmeet.com/2011/07/insertion-sorting/