1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
|
module AufgabeFFP8
where
import Data.Array
import Data.List hiding ((\\))
import Test.QuickCheck
type Nat = Int
-- Minfree basic version
minfree_bv :: [Int] -> Int
minfree_bv xs = head ([0..] \\ xs)
(\\) :: Eq a => [a] -> [a] -> [a]
xs \\ ys = filter (\x -> x `notElem` ys) xs
-- Minfree checklist
minfree_chl :: [Int] -> Int
minfree_chl = search . checklist
search :: Array Int Bool -> Int
search = length . takeWhile id . elems
checklist :: [Int] -> Array Int Bool
checklist xs = accumArray (||) False (0,n)
(zip (filter (<=n) xs) (repeat True))
where n = length xs
-- minfree countlist
minfree_col :: [Int] -> Int
minfree_col = search0 . assocs . countlist
countlist :: [Int] -> Array Int Int
countlist xs = accumArray (+) 0 (0,n) (zip xs (repeat 1))
where n = length xs
sort :: [Int] -> [Int]
sort xs = concat [replicate k x | (x,k) <- assocs $ countlist xs]
search0 :: [(Int, Int)] -> Int
search0 [] = -1
search0((i,0):_) = i
search0 (x:xs) = search0 xs
-- minfree basic daq
minfree_b :: [Int] -> Int
minfree_b xs = if (null ([0..b-1] \\ us))
then (head ([b..] \\ vs))
else (head ([0..] \\ us))
where
b = 1 + (length xs) `div` 2
(us, vs) = partition (<b) xs
-- minfree refined daq
minfree_r :: [Int] -> Int
minfree_r = minfrom_r 0
minfrom_r :: Nat -> [Nat] -> Nat
minfrom_r a xs
| null xs = a
| length us == b-a = minfrom_r b vs
| otherwise = minfrom_r b us
where
b = a + 1 + (length xs) `div` 2
(us, vs) = partition (<b) xs
-- minfree optimized daq (p262)
minfree_o :: [Int] -> Int
minfree_o xs = minfrom_o 0 (length xs, xs)
minfrom_o :: Int -> (Int, [Int]) -> Int
minfrom_o a (n, xs)
| n == 0 = a
| m == b-a = minfrom_o b (n-m, vs)
| otherwise = minfrom_o a (m, us)
where
(us,vs) = partition (<b) xs
b = a + 1 + n `div` 2
m = length us
-- true daq implementations
divideAndConquer :: (p->Bool) -> (p->s) ->(p-> [p]) -> (p-> [s] -> s)-> p -> s
divideAndConquer indiv solve divide combine initPb = dAC initPb
where
dAC pb
| indiv pb = solve pb
| otherwise = combine pb (map dAC (divide pb))
-- minfree basic daq higher order
b_indiv :: Int -> [Int] -> Bool
b_indiv l xs = length xs < l
b_solve :: [Int] -> [Int]
b_solve = id
b_divide :: Int -> [Int] -> [[Int]]
b_divide b xs = [us, vs]
where (us,vs) = partition (<b) xs
b_combine :: Int -> [Int] -> [[Int]] -> [Int]
b_combine b _ (us:vs:[]) = if (null ([0..b-1] \\ us))
then ([b..] \\ vs)
else ([0..] \\ us)
minfree_bhof :: [Int] -> Int
minfree_bhof xs = head $ divideAndConquer (b_indiv (length xs)) b_solve (b_divide b) (b_combine b) xs
where b = 1+(length xs) `div` 2
-- minfree refined daq higher order
|
