ISourceCode

Make the frequent cases fast and the rare case correct

Category Archives: Dynamic Programming

For some given sequence of characters ‘(‘, ‘)’, ‘[', and ']‘ , Find the shortest possible regular brackets sequence, that contains the given character sequence as a sub sequence.

An example of regular bracket sequence is

(), [], (()), ([]), ()[], ()[()]

and the following are not regular bracket sequence

(, [, ), )(, ([)], ([(]

For some given sequence of characters ‘(‘, ‘)’, ‘[', and ']‘ , Find the shortest possible regular brackets sequence, that contains the given character sequence as a sub sequence.

That means

for a given input

([(]

Find an output sequence like this

()[()]

which is the shortest regular bracket sequence that contains the input.

using System;
using System.Collections.Generic;
using System.Collections;
using System.Text;

namespace BracketSequence
{
    class Bracket
    {
        private String[] input;
        private int len;
        private int[,] flag = new int[100, 100];
        private String[,] output = new String[100, 100];

        public Bracket(String[] value)
        {
            this.input = value;
            this.len = input.Length;
            int[,] flag = new int[len, len];
            String[,] output = new String[len, len];
            for (int i = 0; i < len; i++)
                output.SetValue("", i, 0);

            MinimalBracketSeq();
        }

        public String FindSequence()
        {
            return output[0, len - 1];
        }

        private void MinimalBracketSeq()
        {
            for (int i = 0; i < len; i++)
            {
                for (int j = i; j < len; j++)
                {
                    flag[i, j] = int.MaxValue;
                }
            }
            for (int i = len - 1; i >= 0; i--)
            {
                for (int j = i; j < len; j++)
                {
                    if (i == j)
                    {
                        flag[i, j] = 1;
                        if (input[i].Contains("("))
                            output.SetValue("()", i, j);
                        if (input[i].Contains(")"))
                            output.SetValue("()", i, j);
                        if (input[i].Contains("["))
                            output.SetValue("[]", i, j);
                        if (input[i].Contains("]"))
                            output.SetValue("[]", i, j);
                    }
                    else if (j > i)
                    {

                        if (input[i].Contains("(") && input[j].Contains(")"))
                        {
                            if (flag[i + 1, j - 1] < flag[i, j])
                            {
                                flag[i, j] = flag[i + 1, j - 1];
                                output[i, j] = "(" + output[i + 1, j - 1] + ")";
                            }
                        }
                        else if (input[i].Contains("[") && input[j].Contains("]"))
                        {
                            if (flag[i + 1, j - 1] < flag[i, j])
                            {
                                flag[i, j] = flag[i + 1, j - 1];
                                output[i, j] = "[" + output[i + 1, j - 1] + "]";
                            }
                        }
                        for (int k = i; k < j; k++)
                        {
                            if (flag[i, k] + flag[k + 1, j] < flag[i, j])
                            {
                                flag[i, j] = flag[i, k] + flag[k + 1, j];
                                output[i, j] = output[i, k] + output[k + 1, j];
                            }
                        }
                    }
                }
            }
        }
    }
    class Program
    {
        public static void Main(String[] args)
        {
            String[] input = new String[] { "(", "[", "(", "]" };
            Bracket objBkt = new Bracket(input);
            Console.WriteLine("The input is ([(]");
            Console.WriteLine("The shortest regular bracket sequence is");
            Console.WriteLine(objBkt.FindSequence());
            Console.ReadLine();
        }
    }
}

OUTPUT:

tSequence\BracketSequence\bin\Debug>BracketSequence.exe
The input is ([(]
The shortest regular bracket sequence is
()[()]

Wagner–Fischer algorithm – To find Levenshtein distance ( C program )

The Wagner–Fischer algorithm is a dynamic programming algorithm that measures the Levenshtein distance between two strings of characters.

For example, the Levenshtein distance between “kitten” and “sitting” is 3, since the following three edits change one into the other, and there is no way to do it with fewer than three edits:

kitten → sitten (substitution of ‘s’ for ‘k’)
sitten → sittin (substitution of ‘i’ for ‘e’)
sittin → sitting (insertion of ‘g’ at the end).

Computing the Levenshtein distance is based on the observation that if we reserve a matrix to hold the Levenshtein distances between all prefixes of the first string and all prefixes of the second, then we can compute the values in the matrix by flood filling the matrix, and thus find the distance between the two full strings as the last value computed.

                k 	i 	t 	t 	e 	n
	0 	1 	2 	3 	4 	5 	6
s 	1 	1 	2 	3 	4 	5 	6
i 	2 	2 	1 	2 	3 	4 	5
t 	3 	3 	2 	1 	2 	3 	4
t 	4 	4 	3 	2 	1 	2 	3
i 	5 	5 	4 	3 	2 	2 	3
n 	6 	6 	5 	4 	3 	3 	2
g 	7 	7 	6 	5 	4 	4 	3

CODE:

/* http://en.wikipedia.org/wiki/Wagner%E2%80%93Fischer_algorithm */
#include <stdio.h>
#include <math.h>
int d[100][100];
#define MIN(x,y) ((x) < (y) ? (x) : (y))
main()
{
	int i,j,m,n,temp,tracker;
	char s[] = "kitten";
	char t[] = "sitting";
	m = strlen(s);
	n = strlen(t);

	for(i=0;i<=m;i++)
		d[0][i] = i;
	for(j=0;j<=n;j++)
		d[j][0] = j;

	for (j=1;j<=m;j++)
	{
		for(i=1;i<=n;i++)
		{
			if(s[i-1] == t[j-1])
			{
				tracker = 0;
			}
			else{
				tracker = 1;
			}
			temp = MIN((d[i-1][j]+1),(d[i][j-1]+1));
			d[i][j] = MIN(temp,(d[i-1][j-1]+tracker));
		}
	}
	printf("the Levinstein distance is %d\n",d[n][m]);

}

OUTPUT:
$ ./a.exe
the Levinstein distance is 3

References: Wikipedia entry for Levenshtein distance.

Thanks for reading !

Determining the Length of Longest Increasing Subsequence using DP approach and Patience Sorting

Problem Statement :
Given a sequence a_1, a_2,…., a_n, find the largest subset such that for every i < j, ai < aj. – Algorithmist

Example – Wikipedia

In the binary Van der Corput sequence

0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15, …

a longest increasing subsequence is

0, 2, 6, 9, 13, 15.

This subsequence has length six; the input sequence has no seven-member increasing subsequences. The longest increasing subsequence in this example is not unique: for instance,

0, 4, 6, 9, 11, 15

is another increasing subsequence of equal length in the same input sequence.

Approach:

Dynamic Programming: – Algorithmist

There is a straight-forward Dynamic Programming solution in O(n2) time. Though this is asymptotically equivalent to the Longest Common Subsequence version of the solution, the constant is lower, as there is less overhead.

Algorithm Pseudocode:

function lis_length( a )
    n := a.length
    q := new Array(n)
    for k from 0 to n:
        max := 0;
        for j from 0 to k, if a[k] > a[j]:
            if q[j] > max, then set max = q[j].
        q[k] := max + 1;
    max := 0
    for i from 0 to n:
        if q[i] > max, then set max = q[i].
    return max;

Implementation: – Finding Length of LIS using DP

import random
def lis_length( a ):
	n = len(a)
	q = []
    	for x in range (0,n):
		q.append(1)
    	for k in range(0,n):
        	max = 0
        	for j in range (0,k):
			if a[k] > a[j]:
            			if q[j] > max: 
					max = q[j]
        	q[k] = max + 1
    	max = 0
    	for i in range (0,n):
    		if q[i] > max:
			max = q[i]

	return max
a = [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]
value = lis_length(a)
print "Length of LIS =",value

OUTPUT:

labuser@ubuntu:~$ python LISDP.py
Length of LIS = 6

Finding LIS using Patience Sorting – Greedy optimal Strategy

the British use the term Patience to refer to Solitaire with cards

David Aldous and Persi Diaconis wrote the paper entitled: “Longest Increasing Subsequences: From Patience Sorting to the Baik-Deift-Johansson Theorem”.

The Authors explain the Patience game or Solitaire game played in a special manner

“Take a deck of cards labeled 1, 2, 3, … , n. The deck is shuffled, cards are turned up one at a time and dealt into piles on the table, according to the rule

* A low card may be placed on a higher card (e.g. 2 may be placed on 7), or may be put into a new pile to the right of the existing piles.

At each stage we see the top card on each pile. If the turned up card is higher than the cards showing, then it must be put into a new pile to the right of the others. The object of the game is to finish with as few piles as possible”

From studies they suggested a target number = 9 piles, a 5 % chance of getting 9 piles with greedy optimal strategy

import bisect
import random 

def LIS(seq):
    piles = []
        for x in seq:
            new_pile = [x]
            i = bisect.bisect_left(piles, new_pile)
            if i != len(piles):
                    piles[i].insert(0, x)
            else:
                    piles.append(new_pile)    
    
        return len(piles)

a = range(1,53)
lis = []
random.shuffle(a)

for i in range (1,10001):
    random.shuffle(a)
    value = LIS(a)

    lis.append(value)

print dict((item, lis.count(item)) for item in set(lis))

The Authors in the paper explain how this mechanism of forming piles can be used to find LIS

If we define L(π) to be the length of the longest increasing subsequence of a permutation of our card deck, π, then the papers Lemma states

Lemma 1. With deck π, patience sorting played with the greedy strategy ends with exactly L(π) piles. Furthermore, the game played with any legal strategy ends with at least L(π) piles. So the greedy strategy is optimal and cannot be improved by any look-ahead strategy.

Proof. If cards a1 < a2 < … < al appear in increasing order, then under any legal strategy each ai must be placed in some pile to the right of the pile containing ai-1, because the card number on top of that pile can only decrease. Thus the final number of piles is at least l, and hence at least L(π). Conversely, using the greedy strategy, when a card c is placed in a pile other than the first pile, put a pointer from that card to the currently top card c′ < c in the pile to the left. At the end of the game, let al be the card on top of the rightmost pile l. The sequence a1 ← a2 ← … ← al-1 ← al obtained by following the pointers is an increasing subsequence whose length is the number of piles

Further more from Monte-carlo Simulation they were able to conclude by making 10000 trials on a 52 deck card that average number of piles for a random run gives 10-13 piles , but for a successful run with minimum no of piles i.e 7, 8 or 9 the chances are approx 5%.

OUTPUT:

labuser@ubuntu:~$ python patience.py
{8: 47, 9: 501, 10: 1695, 11: 2805, 12: 2606, 13: 1473, 14: 610, 15: 218, 16: 38, 17: 5, 18: 2}
labuser@ubuntu:~$
labuser@ubuntu:~$ python patience.py
{7: 1, 8: 55, 9: 476, 10: 1736, 11: 2852, 12: 2575, 13: 1480, 14: 581, 15: 183, 16: 48, 17: 10, 18: 3}
labuser@ubuntu:~$
labuser@ubuntu:~$ python patience.py
{7: 1, 8: 64, 9: 521, 10: 1713, 11: 2758, 12: 2596, 13: 1498, 14: 595, 15: 207, 16: 38, 17: 6, 18: 3}
labuser@ubuntu:~$
labuser@ubuntu:~$ python patience.py
{7: 2, 8: 48, 9: 497, 10: 1697, 11: 2794, 12: 2588, 13: 1493, 14: 626, 15: 207, 16: 41, 17: 6, 18: 1}
labuser@ubuntu:~$
labuser@ubuntu:~$ python patience.py
{8: 48, 9: 526, 10: 1748, 11: 2735, 12: 2513, 13: 1530, 14: 642, 15: 215, 16: 38, 17: 4, 18: 1}
labuser@ubuntu:~$

import bisect
import random 

def LIS(seq):
	piles = []
    	for x in seq:
        	new_pile = [x]
        	i = bisect.bisect_left(piles, new_pile)
        	if i != len(piles):
            		piles[i].insert(0, x)
        	else:
            		piles.append(new_pile)	
	
    	return len(piles)

a = [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]
value = LIS(a)
print "Length of LIS =",value

labuser@ubuntu:~$ python patience.py
Length of LIS = 6

So for the sequence 7 2 8 1 3 4 10 6 9 5

We have a pile formation shown below with no of piles = 5

Thus the Longest increasing subsequence = 5

Similar results are formed in the paper which helps confirm the 10-13 average pile figure the paper suggests.

Space Complexity:
O(P) to find the Length of LIS for P no of piles. The patience sorting take O(Nlgn) where N is the no of elements are n is no of piles.

Misc Information: As per the Paper
According to D. Aldous and P. Diaconis, patience sorting was first recognized as an algorithm to compute the longest increasing subsequence length by Hammersley, and by A.S.C. Ross and independently Robert W. Floyd as a sorting algorithm. Initial analysis was done by Mallows.

Dynamic Programming Algorithm to find the minimum number of coins to make a certain amount of change out of a given set of denominations

To make a change of 15 from Available denominations 1 2 3 5 we need 3 coins of denomination 5 rather than 5 coins of denomination 3.

SumNeeded = 15
AvailDenominations = [1, 2, 3, 5]

def MinCoins(sum, coinDenominations):
	result = []	
	for i in range(0,sum+1):
		result.append(999)
        
	result[0]=0
	for currentSum in range(1,sum+1):
		for j in range(0,len(AvailDenominations)): 
		  ref = result[currentSum - AvailDenominations[j]] + 1
                  
         	  if AvailDenominations[j] <= currentSum and ref < result[currentSum]:
					                	
				tempA = result[currentSum - AvailDenominations[j]]
				tempB = tempA+1
           			result[currentSum] = tempB
        				
        return result[sum]

SumNeeded = 15
AvailDenominations = [1, 2, 3, 5]
value = MinCoins(SumNeeded, AvailDenominations)
print "Number of coins needed = ",value

OUTPUT:

labuser@ubuntu:~$ python coinproblem.py
Number of coins needed = 3

If input is AvailDenominations = [10, 2, 3, 5] i.e 10+5

labuser@ubuntu:~$ python coinproblem.py
Number of coins needed = 2

Fibonacci Numbers – [Recursion , Iterative using Dynamic Programming , Matrix Property]

In mathematics, the Fibonacci numbers are the numbers in the following integer sequence:

the sequence Fn of Fibonacci numbers is defined by the recurrence relation

with seed values

Closed form solution:
Binet’s formula, even though it was already known by Abraham de Moivre

where

is golden ratio

Matrix form:

A 2-dimensional system of linear difference equations that describes the Fibonacci sequence is

direct formula for the nth element in the fibonacci series:

Python using Matrix property:

>>> import numpy
>>> fib = numpy.matrix([[1,1],[1,0]])
>>> result = fib*fib
>>> result
matrix([[2, 1],
        [1, 1]])
>>> result = fib*fib*fib
>>> result
matrix([[3, 2],
        [2, 1]])
>>> result = fib*fib*fib*fib*fib
>>> result
matrix([[8, 5],
        [5, 3]])

In this Post you can find implementation for finding nth fibonacci number using

1 . Recursion – exponential
2 . Iterative method using Dynamic Programming – O(n)
3 . Matrix Property – O(log n)

For the Run time of the three algorithms please refer to this article from cs.wisc here

Implementation:

import time
def fib_matrix(n):
	i = h = 1
	j = k = 0
	while (n > 0) :
		if (n%2 == 1) : # when n is odd
			t = j*h
			j = i*h + j*k + t
			i = i*k + t
		t = h*h
		h = 2*k*h + t
		k = k*k + t
		n = int(n/2)
	return j
start1 = time.strftime('%s')
value1 = fib_matrix(500000)
#print value1
end1 = time.strftime('%s')
time1 = int(end1) - int(start1)
print "Time to execute the algorithm using matrix property=", time1 ,"Second(s)"

def fib_dp(n):
	a = b = 1
	for i in range(2,n) :
		c = a+b
		a = b
		b = c
	return c
start2 = time.strftime('%s')
value2 = fib_dp(500000)
#print value2
end2 = time.strftime('%s')
time2 = int(end2) - int(start2)
print "Time to execute the algorithm using dynamic programming =", time2 ,"Second(s)"

def fib_rec(n) :
	if (n==1 or n==2) :
		return 1
	return fib_rec(n-1) + fib_rec(n-2)
start3 = time.strftime('%s')
value3 = fib_rec(35)
#print value3
end3 = time.strftime('%s')
time3 = int(end3) - int(start3)
print "Time to execute the algorithm using recursion without dynamic programming =", time3 ,"Second(s)"

OUTPUT:

labuser@ubuntu:~$ python fib.py
Time to execute the algorithm using matrix property= 2 Second(s)
Time to execute the algorithm using dynamic programming = 38 Second(s)
Time to execute the algorithm using recursion without dynamic programming = 19 Second(s)

Note : I had to use input 35 for recursion to capture a run time as its a exponential time algorithm

The matrix method is more efficient than the simple iterative algorithm for larger numbers. For smaller numbers, the simplicity of the iterative algorithm is preferable.

Thanks to Wikipedia for the Theory !

Follow

Get every new post delivered to your Inbox.