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
Use two-dimensional array to solve following problem. Company has four salespeople(1 to 4) who sell five different products (1 to 5). Once day, each salesperson passes slip
Write a program that computes the total payment, tip, and tax for the "ABC" restaurant. This program must have three functions as below: Menu (Show the menu for each custom
Write a program that reads in the size of the side of a square and then prints a hollow square of that size out of asterisks (i.e., *) and blanks.
Write program segments that accomplish each of the following tasks:Calculate the integer part of the quotient when integer a is divided by integer. Calculate the integer remai
Create a program to calculate and displays the number of miles per hour over the speed limit that a speeding driver was doing. The program should ask for the speed limit
Write program which functions similarly to the ATM. A user must be able to give their account number, choose whether they want to make a deposit or a withdrawal
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
Create classes or class templates for the following: Administrative Employess are paid a salary, but they also receive a bonus at regular intervals during the year.