I have a function, test p xs = [(x,y) | (x:ys) <- tails xs, y <- ys, p x y], which returns a list of all tuples which fulfil a predicate such as (\x -> \y -> x*y < 45), for a specified list such as [2..11]. I want to create a maximum maximal independent set: each number in the list is included once, no more and no less. A sample solution for the above predicate and list would be [(2,11),(3,10),(4,9),(5,8),(6,7)].
My current backtracking script is as follows:
notInList pair list
| list == [] = True
| (fst pair) `elem` (tupleToList list) || (snd pair) `elem` (tupleToList list) = False
| otherwise = True
gen pairs final len = do
pair <- pairs
guard $ notInList pair final
if (length final) == len
then return [pair]
else do
next <- gen (delete pair pairs) (pair : final) len
return $ pair : next
tupleToList :: [(a,a)] -> [a]
tupleToList ((a,b):xs) = a : b : tupleToList xs
tupleToList _ = []
I run gen (test (\x -> \y -> x*y < 45) [2..11]) [] 5, which as far as I can tell should backtrack to the right solution eventually, but the script always returns an empty list. I've tried it on other lists and predicates with a valid solution too, and I'm not sure what's going wrong and how I could fix this script to do what I need it to do. I'm not sure whether returning the empty list suggests that it found no solutions, or if it just breaks somewhere in the middle.
This part is suspicious:
guard $ notInList pair final
if (length final) == len
Suppose final is a maximal independent set, so length final == len, where len is the length of the result that you know in advance. Then the guard must be false, so you backtrack without reaching that if.
Put the test of whether you got the final result at the beginning of the function:
gen :: Eq a => [(a, a)] -> [(a, a)] -> Int -> [[(a, a)]]
gen pairs final len | length final == len = return final
gen pairs final len | otherwise = do
-- Take a "pair" out and shadow "pairs" with the remainder.
-- Use "tails" to avoid creating duplicate sets.
-- For example, if you have a list [p1, p2, ...] you want
-- to try to pick p1 then p2, but after backtracking, it's no use trying p2 then p1.
pair : pairs <- tails pairs
guard $ notInList pair final
gen pairs (pair : final) len