summaryrefslogtreecommitdiffstats
path: root/AufgabeFFP3.hs
diff options
context:
space:
mode:
Diffstat (limited to 'AufgabeFFP3.hs')
-rw-r--r--AufgabeFFP3.hs44
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
17safeGet :: [Integer] -> Int -> Integer -- get element of list, default to 0 17safeGet :: [Integer] -> Int -> Integer -- get element of list, default to 0
18safeGet l i 18safeGet l i
19 | i < length l = l !! i 19 | i < length l = l !! i
20 | otherwise = 0 20 | otherwise = 0
21 21
22toBin :: Integer -> [Integer] -- get binary representation of integer 22toBin :: Integer -> [Integer] -- get binary representation of integer
23toBin 0 = [] 23toBin 0 = []
24toBin i = [rem] ++ toBin quot 24toBin i = [rem] ++ toBin quot
25 where ( quot, rem ) = quotRem i 2 25 where ( quot, rem ) = quotRem i 2
26 26
27hasBit :: Integer -> Int -> Bool -- check if the binary representation of a number has the ith bit set 27hasBit :: Integer -> Int -> Bool -- check if the binary representation of a number has the ith bit set
28hasBit num ith = (safeGet (toBin num) ith) == 1 28hasBit num ith = (safeGet (toBin num) ith) == 1
29 29
30getChoice :: Items -> Int -> Items -- choose a subset determined by binary representation of l 30getChoice :: Items -> Int -> Items -- choose a subset determined by binary representation of l
31getChoice l i = concat ( map (choose l) [0..(length l)-1] ) 31getChoice 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
37generator:: Items -> Loads -- get all possible choices (2^n) 37generator:: Items -> Loads -- get all possible choices (2^n)
38generator l = map ( getChoice l ) [1..num] 38generator l = map ( getChoice l ) [1..num]
39 where num = (2^(length l)) - 1 39 where num = (2^(length l)) - 1
40 40
41transformer :: Loads -> [LoadWghtVal] -- calc sum of weight and value for all lists of items 41transformer :: Loads -> [LoadWghtVal] -- calc sum of weight and value for all lists of items
42transformer l = map trans l 42transformer l = map trans l
43 43
44trans :: Load -> LoadWghtVal -- worker of transformer 44trans :: Load -> LoadWghtVal -- worker of transformer
45trans load = (load, weight, value) 45trans 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
50getWeight :: LoadWghtVal -> Weight 50getWeight :: LoadWghtVal -> Weight
51getWeight (_, w, _) = w 51getWeight (_, w, _) = w
@@ -58,16 +58,16 @@ filter max l = [ x | x <- l, getWeight x <= max ]
58 58
59selector :: [LoadWghtVal] -> [LoadWghtVal] -- get those with max val 59selector :: [LoadWghtVal] -> [LoadWghtVal] -- get those with max val
60selector l = [ x | x <- l, getVal x == max ] 60selector l = [ x | x <- l, getVal x == max ]
61 where max = maximum $ map getVal l 61 where max = maximum $ map getVal l
62 62
63selector1 :: [LoadWghtVal] -> [LoadWghtVal] -- all with max val 63selector1 :: [LoadWghtVal] -> [LoadWghtVal] -- all with max val
64selector1 = selector 64selector1 = selector
65 65
66selector2 :: [LoadWghtVal] -> [LoadWghtVal] -- get ones with min weight 66selector2 :: [LoadWghtVal] -> [LoadWghtVal] -- get ones with min weight
67selector2 l = [ x | x <- best, getWeight x == min ] 67selector2 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
78binom :: (Integer, Integer) -> Integer 78binom :: (Integer, Integer) -> Integer
79binom (n, k) 79binom (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
84binomS :: (Integer, Integer) -> Integer 84binomS :: (Integer, Integer) -> Integer
85binomS (n, k) = pd !! fromInteger n !! fromInteger k 85binomS (n, k) = pd !! fromInteger n !! fromInteger k
86 86
87-- calc table 87-- calc table
88binomMemoTable :: [[Integer]] 88binomMemoTable :: [[Integer]]
89binomMemoTable = [ [ binomM (n, k) | k <- [0..] ] | n <- [0..] ] 89binomMemoTable = [ [ 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
93binomM :: (Integer, Integer) -> Integer 93binomM :: (Integer, Integer) -> Integer
94binomM (n, k) 94binomM (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