CODEWITHSUNDEEP
listhaskellinfinite
nub
nub

Reputation: 1

Haskell: how to treat big combinatorial Lists?

just recently I tried to write a program which basically simulates a simple system from an Online Game. The idea behind that is, to let the program calculate the most efficient set of items for the most possible stat efficiency from a set. To clarify this a bit more: you've got 8 item Slots and 74 different items, you can't use any item twice, and it doesn't matter which item is in which slot. I'am not even yet trying to calculate one set of stats, I'am stuck way earlier!

So the problem with this is the number of possibilities which are (74^8) before filtering and (74 choose 8) after filtering. My program already starts lagging when I just try head(permu' 2). Since I know Haskell is supposed to work with infinite Lists, how does it work with a List of 899 trillion entries? Well I know obviously it takes a lot of capacity for the PC but that's why I am here to ask:

How do I treat a big List in Haskell so that I can work with it?

the function simplified looks like this:

quicksort :: (Ord a) => [a] -> [a]
quicksort [] = []
quicksort [a] = [a]
quicksort (x:xs) = (quicksort [y | y <- xs, y <= x]) ++ [x] ++ (quicksort [z | z <- xs , z > x])

eliminatedouble [] = []
eliminatedouble (x:xs) = if x `elem` xs then eliminatedouble xs else x:(eliminatedouble xs)

permu' n | n>8 = error "8 is max"
         | otherwise = eliminatedouble (filter allSatisfied (generate n))
   where
      generate 0 = [[]]
      generate x = [quicksort (a:xs) | a <- [1..74], xs <- generate (x-1)]
      allSatisfied [] = True
      allSatisfied (x:xs) = (checkConstraint x xs) && (allSatisfied xs)
      checkConstraint x xs = not (doubled x xs)
      doubled x xs = x `elem` xs

would be interesting to know how to do all this way cheaper.

Thanks in advance, regards.

Upvotes: 0

Views: 151

Answers (1)

Daniel Wagner
Daniel Wagner

Reputation: 152707

You're making this much more difficult than it needs to be.

choose 0 xs = [[]]
choose n [] = []
choose n (x:xs) = map (x:) (choose (n-1) xs) ++ choose n xs

In my interpreter, choose 5 [1..74] takes about 22 seconds to compute all the entries and choose 6 [1..74] takes 273 seconds. Additionally, choose 8 [1..74] starts chugging through combinations straight away; I estimate that it would take about 6 hours to generate them all. N.B. that this is in the interpreter, with no optimization or other fanciness going on; possibly it could go much faster if you give GHC a chance to figure out how.

Assuming that you intend to do some nontrivial computation on each element of choose 8 [1..74], I suggest you either schedule a largish chunk of time or else think about solutions that do not do an exhaustive search -- perhaps using some heuristics to get an approximate answer, or figuring out how to do some pruning to cut out large, uninteresting swaths of the search space.

Upvotes: 3

Related Questions