Back to Questions
3.0k
views2
comments
Functional way to do Dynamic Programming?
f#functionalserver

What's a functional way to do dynamic programming over a matrix?

E.g., here's the Longest Common Subsequence pseudocode from Cormen et al algorithms book:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

# Longest Common Subsequence Algorithm
# CLR 2ed, p. 353
LCS-length(X,Y)
m <- length[X]
n <- length[Y]

for i <- 1 to m
	do c[i,0] <- 0

for j <- 0 to n
	do c[0,j] <- 0

for i <- 1 to m
	do for j <- 1 to n
		do if x_i = x_j
			then c[i,j] <- c[i-1, j-1] + 1
				 b[i,j] <- NW_arrow
			else if c[i-1,j] >= c[i,j-1]
				then c[i,j] <- c[i-1,j]
					 b[i,j] <- N_arrow
				else c[i,j] <- c[i,j-1]
					 b[i,j] <- W_arrow
return <c,b>

Arrgh, this dog server eats my whitespaces! Here's a link to Google book:

[link:books.google.com][link:www.google.com]

-- is there an elegant FP way to handle it, different from a list of points like ConcurrentLife solution?

.

Hi,

I haven't tried with your example, but this article might help you for dynamic programming:
[link:laurent.le-brun.eu]

Another technique useful for dynamic programming is the use of an array with lazy values. I'll try with your example later.

Laurent.

By on 3/8/2008 3:38 AM ()

You can compute the length matrix (called "c" in the book) in this way:

1
2
3
4
5
6

let X = [|'B'; 'D'; 'C'; 'A'; 'B'; 'A'|]
let Y = [|'A'; 'B'; 'C'; 'B'; 'D'; 'A'; 'B'|]
let rec store = Array2.init (X.Length+1) (Y.Length+1) <| fun i j ->
  lazy if i = 0 || j = 0 then 0
       elif X.[i-1] = Y.[j-1] then store.[i-1, j-1].Force() + 1
       else max <| store.[i, j-1].Force() <| store.[i-1, j].Force()

And then, print it:

1

store |> Array2.map (fun x -> x.Force()) |> print_any
By on 3/8/2008 7:09 AM ()

    Topic tags

    IntelliFactory Offices Copyright (c) 2011-2012 IntelliFactory. All rights reserved.
    Home | Products | Consulting | Trainings | Blogs | Jobs | Contact Us | Terms of Use | Privacy Policy | Cookie Policy     		Built with WebSharper