CODEWITHSUNDEEP
haskell
Mannso
Mannso

Reputation: 3

Haskell optimization program

Have the task I need to implement the function Change, which will take the value and split it into the possible combinations from list of coins(random list) Example:

coins = [2,3,7]
GHCi> change 7
[[2,2,3],[2,3,2],[3,2,2],[7]]

That's what I did:

coins :: Num a => [a] 
coins = [2, 3, 7]

change :: (Ord a, Num a) => a -> [[a]]
change n =  uniqEl (filter (\x -> sum x == n) take ()(subsequences (replic' n coins coins)))

replic' n x y | n == 1 = y
              | otherwise = replic' (n-1) x (y ++ x) 

uniqEl :: Eq a => [a] -> [a]
uniqEl [] = []
uniqEl (x:xs) = if (x `elem` xs) then uniqEl xs else x : (uniqEl xs)

But this code is very slow. Help to make this program more quickly. As part of the job it is said that this task is easily done with the help of generators lists and recursion. Thank you in advance for your help.

Upvotes: 0

Views: 138

Answers (3)

koki
koki

Reputation: 352

Use MemoCombinators. This is fast ! Pls. try change 100

import Data.List
import qualified Data.MemoCombinators as Memo

coins :: [Int]
coins = [2,3,7]

change :: Int -> [[Int]]
change = Memo.integral change'
change' 0 = []
change' n = do
  x <- [c | c <- coins, c <= n]
  if x == n
    then return [x]
    else do
      xs <- change (n - x)
--    if (null xs)
--      then return [x]
--      else if x < (head xs)
--        then []
--        else return (x:xs)
      return (x:xs)

Upvotes: 0

koki
koki

Reputation: 352

import Data.List

change :: [Int] -> Int -> [[Int]]
change _ 0 = []
change coins n = do
  x <- [c | c <- coins, c <= n]
  if x == n
    then return [x]
    else do
      xs <- change coins (n - x)
--    if (null xs)
--      then return [x]
--      else if x < (head xs)
--        then []
--        else return (x:xs)
      return (x:xs)

change' :: Int -> [[Int]]
change' = change [2,3,7]

test7 = change' 7
test6 = change' 6
test5 = change' 5
test4 = change' 4

Upvotes: 1

Arnon
Arnon

Reputation: 2237

You're doing a lot of filtering, eleming and so on, and placing a lot of constraints on the data types. Think of this more as a dynamic problem, that you constantly need to figure out how many ways there are to return change for a total amount.

Once you have found the amount of possibilities for a specific coin, you can remove it from the list.

Here is my proposed solution wrapped up in one function. In the list comprehension, note that I assign values to the remaining variable, and that these values range from [0,total], with jumps every x, where x is the denomination. For example, if you had to calculate how many times $0.25 goes into a $2 total, that list comprehension ends up doing: [countChange 2, countChange 1.75,countChange 1.5, countChange 1.25,...], but also these next iterations of countChange don't include the 0.25 coin - because we just "tested" that.

-- Amount to return -> List of Coin denominations available
countChange :: Integer -> [Integer] -> Integer
countChange _ [] = 0 -- No coins at all, so no change can be given
countChange 0 _ = 1 -- Only one way to return 0 change
countChange total (x:xs) = sum [countChange (total-remaining) xs | remaining <- [0,x..total]]

Upvotes: 0

Related Questions