diff options
Diffstat (limited to 'AufgabeFFP3.hs')
| -rw-r--r-- | AufgabeFFP3.hs | 44 |
1 files changed, 22 insertions, 22 deletions
diff --git a/AufgabeFFP3.hs b/AufgabeFFP3.hs index 459f510..8b1d748 100644 --- a/AufgabeFFP3.hs +++ b/AufgabeFFP3.hs | |||
| @@ -16,36 +16,36 @@ type MaxWeight = Weight | |||
| 16 | 16 | ||
| 17 | safeGet :: [Integer] -> Int -> Integer -- get element of list, default to 0 | 17 | safeGet :: [Integer] -> Int -> Integer -- get element of list, default to 0 |
| 18 | safeGet l i | 18 | safeGet l i |
| 19 | | i < length l = l !! i | 19 | | i < length l = l !! i |
| 20 | | otherwise = 0 | 20 | | otherwise = 0 |
| 21 | 21 | ||
| 22 | toBin :: Integer -> [Integer] -- get binary representation of integer | 22 | toBin :: Integer -> [Integer] -- get binary representation of integer |
| 23 | toBin 0 = [] | 23 | toBin 0 = [] |
| 24 | toBin i = [rem] ++ toBin quot | 24 | toBin i = [rem] ++ toBin quot |
| 25 | where ( quot, rem ) = quotRem i 2 | 25 | where ( quot, rem ) = quotRem i 2 |
| 26 | 26 | ||
| 27 | hasBit :: Integer -> Int -> Bool -- check if the binary representation of a number has the ith bit set | 27 | hasBit :: Integer -> Int -> Bool -- check if the binary representation of a number has the ith bit set |
| 28 | hasBit num ith = (safeGet (toBin num) ith) == 1 | 28 | hasBit num ith = (safeGet (toBin num) ith) == 1 |
| 29 | 29 | ||
| 30 | getChoice :: Items -> Int -> Items -- choose a subset determined by binary representation of l | 30 | getChoice :: Items -> Int -> Items -- choose a subset determined by binary representation of l |
| 31 | getChoice l i = concat ( map (choose l) [0..(length l)-1] ) | 31 | getChoice l i = concat ( map (choose l) [0..(length l)-1] ) |
| 32 | where | 32 | where |
| 33 | choose l pos | 33 | choose l pos |
| 34 | | hasBit (fromIntegral i) pos = [ l !! pos ] | 34 | | hasBit (fromIntegral i) pos = [ l !! pos ] |
| 35 | | otherwise = [] | 35 | | otherwise = [] |
| 36 | 36 | ||
| 37 | generator:: Items -> Loads -- get all possible choices (2^n) | 37 | generator:: Items -> Loads -- get all possible choices (2^n) |
| 38 | generator l = map ( getChoice l ) [1..num] | 38 | generator l = map ( getChoice l ) [1..num] |
| 39 | where num = (2^(length l)) - 1 | 39 | where num = (2^(length l)) - 1 |
| 40 | 40 | ||
| 41 | transformer :: Loads -> [LoadWghtVal] -- calc sum of weight and value for all lists of items | 41 | transformer :: Loads -> [LoadWghtVal] -- calc sum of weight and value for all lists of items |
| 42 | transformer l = map trans l | 42 | transformer l = map trans l |
| 43 | 43 | ||
| 44 | trans :: Load -> LoadWghtVal -- worker of transformer | 44 | trans :: Load -> LoadWghtVal -- worker of transformer |
| 45 | trans load = (load, weight, value) | 45 | trans load = (load, weight, value) |
| 46 | where | 46 | where |
| 47 | weight = sum $ map fst load | 47 | weight = sum $ map fst load |
| 48 | value = sum $ map snd load | 48 | value = sum $ map snd load |
| 49 | 49 | ||
| 50 | getWeight :: LoadWghtVal -> Weight | 50 | getWeight :: LoadWghtVal -> Weight |
| 51 | getWeight (_, w, _) = w | 51 | getWeight (_, w, _) = w |
| @@ -58,16 +58,16 @@ filter max l = [ x | x <- l, getWeight x <= max ] | |||
| 58 | 58 | ||
| 59 | selector :: [LoadWghtVal] -> [LoadWghtVal] -- get those with max val | 59 | selector :: [LoadWghtVal] -> [LoadWghtVal] -- get those with max val |
| 60 | selector l = [ x | x <- l, getVal x == max ] | 60 | selector l = [ x | x <- l, getVal x == max ] |
| 61 | where max = maximum $ map getVal l | 61 | where max = maximum $ map getVal l |
| 62 | 62 | ||
| 63 | selector1 :: [LoadWghtVal] -> [LoadWghtVal] -- all with max val | 63 | selector1 :: [LoadWghtVal] -> [LoadWghtVal] -- all with max val |
| 64 | selector1 = selector | 64 | selector1 = selector |
| 65 | 65 | ||
| 66 | selector2 :: [LoadWghtVal] -> [LoadWghtVal] -- get ones with min weight | 66 | selector2 :: [LoadWghtVal] -> [LoadWghtVal] -- get ones with min weight |
| 67 | selector2 l = [ x | x <- best, getWeight x == min ] | 67 | selector2 l = [ x | x <- best, getWeight x == min ] |
| 68 | where | 68 | where |
| 69 | min = minimum $ map getWeight best | 69 | min = minimum $ map getWeight best |
| 70 | best = selector l | 70 | best = selector l |
| 71 | 71 | ||
| 72 | 72 | ||
| 73 | -- pascal's triangle from exercise 1 | 73 | -- pascal's triangle from exercise 1 |
| @@ -77,22 +77,22 @@ pd = [[1]] ++ (zipWith (\x y -> zipWith (+) ([0] ++ x) (y ++ [0])) pd pd) | |||
| 77 | -- naive | 77 | -- naive |
| 78 | binom :: (Integer, Integer) -> Integer | 78 | binom :: (Integer, Integer) -> Integer |
| 79 | binom (n, k) | 79 | binom (n, k) |
| 80 | | k == 0 || n == k = 1 | 80 | | k == 0 || n == k = 1 |
| 81 | | otherwise = binom (n-1, k-1) + binom (n-1, k) | 81 | | otherwise = binom (n-1, k-1) + binom (n-1, k) |
| 82 | 82 | ||
| 83 | -- stream using pascal | 83 | -- stream using pascal |
| 84 | binomS :: (Integer, Integer) -> Integer | 84 | binomS :: (Integer, Integer) -> Integer |
| 85 | binomS (n, k) = pd !! fromInteger n !! fromInteger k | 85 | binomS (n, k) = pd !! fromInteger n !! fromInteger k |
| 86 | 86 | ||
| 87 | -- calc table | 87 | -- calc table |
| 88 | binomMemoTable :: [[Integer]] | 88 | binomMemoTable :: [[Integer]] |
| 89 | binomMemoTable = [ [ binomM (n, k) | k <- [0..] ] | n <- [0..] ] | 89 | binomMemoTable = [ [ binomM (n, k) | k <- [0..] ] | n <- [0..] ] |
| 90 | 90 | ||
| 91 | -- using memoisation | 91 | -- using memoisation |
| 92 | -- base case or recursion formula using lookup table | 92 | -- base case or recursion formula using lookup table |
| 93 | binomM :: (Integer, Integer) -> Integer | 93 | binomM :: (Integer, Integer) -> Integer |
| 94 | binomM (n, k) | 94 | binomM (n, k) |
| 95 | | k == 0 || n == k = 1 | 95 | | k == 0 || n == k = 1 |
| 96 | | otherwise = get (n-1) (k-1) + get (n-1) (k) | 96 | | otherwise = get (n-1) (k-1) + get (n-1) (k) |
| 97 | where get n k = binomMemoTable !! fromInteger n !! fromInteger k | 97 | where get n k = binomMemoTable !! fromInteger n !! fromInteger k |
| 98 | 98 | ||
