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
Calculate a person's net pay after subtracting federal income tax. The program should ask the user to enter the person's name, social security number, gross pay, and the num
Write a program in Visual Basic 2010 to compute tips for services rendered. The program should request the person's occupation, the amount of the bill and the percentage
Write a program that accepts six(6) pairs of values from the user and then calculates and stores the difference of each pair of values in an array.
Develop a mock-up of each of these reports, and get customer approval of these mock-ups. Write pseudo code that will generate these reports from the data files, using a CASE t
Create a simulation race between the tortoise and the hare. For this project, use random-number generation to move the creatures. To make things more interesting, the animal
Write the program which processes test data. Output must be student's ID, followed by answers, followed by test score, followed by test grade. Suppose the following grade sca
Implement the Shape hierarchy shown in following figure. Each TwoDimensionalShape should contain method getArea to calculate the area of the two-dimensional shape.
Write down the program in class FlowerCounter which calculates the cost of flowers sold at flower stand. Five types of flowers-petunia, pansy, rose, violet, and camation- ar