Monthly Archives: July 2013

Program to generate all permutations of a given string

This is one of the famous programming problems. In this post, we discuss an algorithm to generate all permutations of a given array and how to implement the same in Java.This is also one of the beautiful example to understand recursion.

We discuss a recursive algorithm as it is simple to understand and implement. Let us define this problem in terms of itself. This is the first step in the process of forming a recursive solution.

Let us consider an array of length n. We can fix the first element (Observe that there are n possible ways) and try to generate permutations with the remaining (n-1) elements. Generating permutations of (n-1) elements is again the original problem, only with the smaller input size. Hence we can easily design  a recursive algorithm.

Here is how the algorithm works. Let us fix array[0] as the first element, and recursively find permutations for the remaining (n-1) elements. Next we will swap array[0] with array[1], and call the same function recursively for (n-1) elements and so on… for others( array[2], array[3],… array[n-1]). After every recursive call, we swap back the elements so that the original order is restored.

Let us understand this with a small example. The following is the recursion tree for a simple input array [1,2,3]. The elements marked in Red are the elements that are swapped.

Here is the Java implementation of the algorithm.

import java.util.Scanner;
public class Permutation {
public static void main(String[] args)
{
Scanner reader = new Scanner(System.in);
String input = reader.nextLine();
printPermutations(input.toCharArray(),0);
}
public static void printPermutations(char[] input,int start)
{
//Base case for recursion, if start index is the end;
//no need to recurse further, just print the pattern
if( start == input.length-1 )
{
for(int i = 0; i < input.length; i++)
System.out.print(input[i]);
System.out.println();
}
else
{
//fix the first character and generate per
for( int i = start; i < input.length; i++)
{
//swap start element, with ith element
if( i!= start) // swap only if start, and i are different
{
char t = input[start];
input[start] = input[i];
input[i] = t;
}

printPermutations(input,start+1);
//swap back the elements
if( i != start)
{
char t = input[start];
input[start] = input[i];
input[i] = t;
}
}
}
}
}

Program to generate Magic square

A Magic square is a two dimensional arrangement of numbers ( from 1 to n2 ) in an n x n matrix such that adding all the numbers from any row, column or principal diagonal gives the same result.

for example the following matrix is a magic square of size 3 X 3

8  1  6
3  5  7
4  9  2

Here the by summing up any row,column, or diagonal, result is 15.

There is a simple algorithm for generating square of odd order ( 3 X 3, 5 X 5,… )

We start by filling 1 in  middle element in the first row. Then we move one step right and one step above. We will check if there is a number already placed in that slot. If not we put 2 there and follow the same algorithm for subsequent numbers.
If a number is already there, we move down one step and place the next number there.

In moving right,if we reach the last column, we wrap to the first column. Similarly while moving up, if we reach first row, we wrap to the last row. This essentially a cyclic iteration.

The following snapshots shows the step by step filling up of the grid.

0 1 0  0 1 0   0 1 0   0 1 0   0 1 0   0 1 6   0 1 6   8 1 6   8 1 6
0 0 0->0 0 0-> 3 0 0-> 3 0 0-> 3 5 0-> 3 5 0 ->3 5 7-> 3 5 7-> 3 5 7
0 0 0  0 0 2   0 0 2   4 0 2   4 0 2   4 0 2   4 0 2   4 0 2   4 9 2

In the first step, when we move right, we reach the last column in the first row. We can not go up, so we move to last row and place 2 there.
In the next step, we can not move from last column, so we move to first column, move up by one position and place 3 there. In the next step, if we move right, move up, we find that cell is already filled with 1. Hence we move down one step and place 4. You can analyze the remaining moves in a similar way.

The following Java program implements the above algorithm. Remember to pass only odd number as parameter.

import java.util.Scanner;

/**
* Created with IntelliJ IDEA.
* User: Ravi
* Date: 7/26/13
* Time: 4:53 PM
*/
public class MagicSquare {
public static void main(String[] args)
{
Scanner reader = new Scanner(System.in);
int n = reader.nextInt();
int[][] board = new int[n][n]; //automatically initialized with '0'

int row = 0; // start with first row
int col = n/2; //middle element
int num = 1; // number to be filled
// n X n grid contains n^2 numbers
while ( num <= n*n )
{
board[row][col] = num;
num++;

//increment column, when reaches last, start from the beginning
int tempCol = (col + 1)%n;
//decrement row, when last row is reached, move to the first
int tempRow = (row - 1) >= 0 ? row-1 : n-1;

//If the target cell is not empty, move to next row
if( board[tempRow][tempCol] != 0 )
{
row = (row+1)%n;
}
else
{
row = tempRow;
col = tempCol;
}
}
//print the magix square
for( int i = 0 ; i < n ; i++)
{
for( int j = 0 ; j < n ; j++)
{
System.out.print(board[i][j] + " ");
}
System.out.println();
}
}
}

Longest Increasing Subsequence problem

Given an array of numbers, we have to find the longest sub sequence of that array which is strictly increasing.

For example in the following array
[8 1 4 2 7 9 5]

{8,9}
{1,4,7,9}
{1,2,7,9}

{1,2,5}
{1,2,7}
{1,2,9}

are some of the increasing sub-sequences. The second and third are the longest increasing sub sequences with length 4. Our job is to find the length of the longest increasing sub sequence.
There are various ways of solving this problem. In this post we will use the following algorithm to find the length of the longest increasing sub sequence.

We take one by one element from the array and insert them into a sorted set data structure. (TreeSet class in Java is one such implementation of sorted set. Please see the program details below)
Once the element is inserted, we will see if it is appended at the end. If it is, we proceed to the next element in the array. If it is not, we will delete the next element to newly inserted element.
At the end, the size of the sorted set is the length of the longest increasing sub sequence.

To understand this further, let us look at the contents of the sorted set in each iteration

Iteration 1: {8} – element added at the end
Iteration 2: {1} – 1 added before 8, so 8 got deleted
Iteration 3: {1,4} – 4 added at the end
Iteration 4: {1,2} – 2 added before 4, 4 got deleted
Iteration 5: {1,2,7} – 7 added at the end
Iteration 6: {1,2,7,9} – 9 added at the end
Iteration 7: {1,2,5,9} – 5 added before 7, 7 got deleted

So the size{1,2,5,9} = 4 is the required answer. However, the sequence may not reflect the longest sequence. It will only indicate the length of it.

The following Java program implements the above algorithm. In this program you can see how the TreeSet data struture is used. This data structure maintains the sorted order when the elements are inserted. It does not allow duplicates to be inserted. The add() method inserts the element if there is no such element exists in the set and it returns true if the element is newly added, otherwise it returns false.

The last() method returns the last element in the set. The higher() method returns the least element which is greater than the given element. All these methods are used in the following program.

 
import java.util.TreeSet;

public class LIS {
public static void main(String[] args)
{
Test1();
Test2();
Test3();
Test4();
Test5();
}
public static void Test1()
{
int [] array = {8,1,4,2,7,9,5};
System.out.println("LIS{8,1,4,2,7,9,5}: " + getLengthOfLIS(array));
}
public static void Test2()
{
int [] array = {1};
System.out.println("LIS{1}: " + getLengthOfLIS(array));
}
public static void Test3()
{
int [] array = {2,1};
System.out.println("LIS{2,1}: " + getLengthOfLIS(array));
}
public static void Test4()
{
int [] array = {1,2,3,4,5};
System.out.println("LIS{1,2,3,4,5}: " + getLengthOfLIS(array));
}
public static void Test5()
{
int [] array = {5,4,3,2,1};
System.out.println("LIS{5,4,3,2,1}: " + getLengthOfLIS(array));
}
public static int getLengthOfLIS(int[] array)
{
TreeSet<Integer> s = new TreeSet<Integer>();
for( int i = 0 ; i < array.length ; i++)
{
//if array[i] is newly added?
if( s.add(array[i]) )
{
//if array[i] is not the last element?
if( array[i] != s.last() )
{
//remove it's next element; s.higher() gives the least element
//which is greater than array[i]
s.remove(s.higher(array[i]));
}
}
}
return s.size();
}
}

This method runs in linear time (O(n)) and O(n) extra space for the sorted set.