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

Assignment Help
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 to assign the integer values 1 through 25 to a 25-element integer array. Then, print the array as five separate lines, each containing five elements separate
Calculate the running average for residential and business customer spending. Print all customer's bill to a single file and the end of the file you should have the average
Write a Bash shell script named phone.bsh that prompts the user the to enter first or last or any portion of person's name, so that can be found the appropriate entry in
Write class named ParkingMeter containing:A method named tick that accepts no parameters and returns no value. tick decreases value of timeLeft by 1, but only if value of ti
Many contemporary languages allow two kinds of comments, one in which delimiters are used on both ends (for multiple line comments), and one in which a delimiter marks on
Let i measure the number of iterations of the inner loop of B3 and B4 (which count of iterations we cannot know), and let j measure the number of iterations of the outer loo
Create a simple command line program that simulates the rolling of a pair of six sided dice a user given number of times. The number of times to roll the pair of dice should
Architecting web-applications using web-services has advantages. Forexample, you can gain increased security. Describe other advantages otherthan security gained by using we