Write a haskell program to calculates a balanced partition
Course:- Programming Languages
Reference No.:- EM13167

Assignment Help
Expertsmind Rated 4.9 / 5 based on 47215 reviews.
Review Site
Assignment Help >> Programming Languages

Write a program in Haskell which calculates a balanced partition of N items where each item has a value between 0 and K such that the difference b/w the sum of the values of first partition, S1, and the sum of the values of the second partition, S2, is minimized. Each partition does not have to have the same number of elements.

One classical way to do this is by using dynamic programming. For dynamic programming to be efficient you should avoid recalculating intermediate results. This can be tricky in a functional language as it does not store state information. The solution is data memorization. Intermediate results are stored is a data structure when they are initially calculated and then simply retrieved when needed.

Here is an example of data memorization in calculating a Fibonacci number.

import Data.Array

fibonacci :: Integer -> Integer
fibonacci n = memo!n
  memo = array (0, n) [ (i, fib i) | i <- [0..n] ]
  fib 0 = 0
  fib 1 = 1
  fib i = memo!(i-1) + memo!(i-2)

This example uses the Array module. Since Haskell is a lazy programming language it only calculates a function when it is needed.

Implement a solution to the balanced partition in Haskell.

Put your comment

Ask Question & Get Answers from Experts
Browse some more (Programming Languages) Materials
Write a program which uses while loops to perform following steps: Prompts user to input two integers: firstNum and secondNum. (firstNum must be less than secondNum).
How will the matrix above result if we execute the command and Write a command delete_object(sub1,sub1) that will delete any occurrences of sub1 if sub1has the right m with it
Build your own maze and make it so easy so i can understand it. try to use for while statement. it is an easy task so please do not make it complicated and follow the instru
Write a program that display a company payroll report in a list box. the program should read each employees name, hourly rate and hours worked from a file and produce a r
Though looking very efficient in terms of a quick jump to distant code why may it cause some efficiency problems during execution? Explain - Show (draw) the runtime-stack wit
Write a program that reads two times in military format (e.g., 0900, 1730) and prints the number of hours and minutes between the two times. Note that the first time can com
Write a void function display_exer() that display in a nicely formated way the eat members of an exerclass object. Pass the object to the function by reference.
Write a few lines of code (need not be a separate function) to: Concatenate strings a and b separated by space into a string f. Print it.