为什么我的回溯总是 return 一个空列表？

Question

我有一个函数，test p xs = [(x,y) | (x:ys) <- tails xs, y <- ys, p x y]，它 returns 满足谓词的所有元组的列表，例如 (\x -> \y -> x*y < 45)，对于指定的列表，例如 [2..11] .我想创建一个最大最大独立集：列表中的每个数字都包含一次，不多也不少。上述谓词和列表的示例解决方案是 [(2,11),(3,10),(4,9),(5,8),(6,7)].

我目前的回溯脚本如下：

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 运行 gen (test (\x -> \y -> x*y < 45) [2..11]) [] 5，据我所知最终应该回溯到正确的解决方案，但脚本总是 returns 一个空列表。我也用有效的解决方案在其他列表和谓词上尝试过它，但我不确定出了什么问题以及如何修复此脚本以执行我需要它执行的操作。我不确定返回空列表是否表明它没有找到解决方案，或者它是否只是在中间某处中断。

Answer 1

这部分可疑：

 guard $ notInList pair final
 if (length final) == len

假设final是一个最大独立集，所以length final == len，其中len是你预先知道的结果的长度。那么守卫一定是假的，所以你没有到达 if.

就原路返回

把是否得到最终结果的测试放在函数的开头：

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

为什么我的回溯总是 return 一个空列表？

Why does my backtracking always return an empty list?

haskell

backtracking