1

我希望有人可以帮助找出我的错误所在。打电话g 3 4 0 2 (M.empty,0) []，我希望[[2,1,0,1]]结果。相反，我看到[[2,1,0,1],[2,1,0,1]].

该程序应该m通过每次将不同的数字添加到列表中来累积不同的长度数字模式，到达时返回向下，到达时返回n-1向上0。当向上和向下方向递归调用函数时，明显的问题发生在中间。

如果我像这样注释掉第 11 行：

else g n m (digitCount + 1) (lastDigit + 1) (hash',hashCount') (lastDigit:digits)
  -- g n m (digitCount + 1) (lastDigit - 1) (hash',hashCount') (lastDigit:digits)

我得到正确的结果[]

就像注释掉第 11 行并将第 10 行修改为：

else g n m (digitCount + 1) (lastDigit - 1) (hash',hashCount') (lastDigit:digits)

再次，正确的结果[[2,1,0,1]]

为什么g使用接线员拨打两次电话时++，我得到[2,1,0,1]的是两个而不是一个？在我看来，每个结果都g应该是不同的，因为在任何递归调用中，不同的数字顺序正在（或应该）累积。

提前致谢。

import qualified Data.Map as M

g :: Int -> Int -> Int -> Int -> (M.Map Int Bool, Int) -> [Int] -> [[Int]]
g n m digitCount lastDigit (hash,hashCount) digits
  | digitCount == m = if test then [reverse digits] else []
  | otherwise       =
      if lastDigit == 0
         then g n m (digitCount + 1) (lastDigit + 1) (hash',hashCount') (lastDigit:digits)
         else if lastDigit == n - 1
                 then g n m (digitCount + 1) (lastDigit - 1) (hash',hashCount') (lastDigit:digits)
                 else g n m (digitCount + 1) (lastDigit + 1) (hash',hashCount') (lastDigit:digits)
                   ++ g n m (digitCount + 1) (lastDigit - 1) (hash',hashCount') (lastDigit:digits)
 where test = hashCount == n
       (hash',hashCount') = 
         if test
            then (M.empty,hashCount)
            else case M.lookup lastDigit hash of
                   Just anyting -> (hash,hashCount)
                   Nothing      -> (M.insert lastDigit True hash,hashCount + 1)
4

3 回答 3

3

现在你已经让它工作了，这里有一个更通用的方法。

我们需要遍历解决方案树。

    data S a = Solution a | Explore [S a]

解决方案是这棵树的叶子，探索是要探索的选项列表。

    -- this is very much unfoldr-like
    generator :: [S a] -> [a]
    generator [] = []
    generator (Solution a: ss) = a: generator ss
    generator (Explore ps: ss) = generator $ ss ++ ps

现在，给定一个“可能的解决方案”列表，生成一个解决方案列表。生成器模式匹配探索，并将要探索的解决方案列表附加到列表的末尾。通过这种方式，我们正在探索解决方案的广度优先，这样我们就可以处理非终止分支。（深度优先无法脱离非终止分支）。这当然是以内存为代价的，但是即使对于具有无限数量的解决方案的问题，您也可以找到有限数量的解决方案。

现在，为您的问题生成解决方案的函数：

    g :: Int -> Int -> [S [Int]]
    g n m = [Explore $ g' [i] (S.singleton i) | i <- [1..n-1]]  where
      g' is@(h:_) ms
       | h < 0 || h >= n || length is > m = [] --no solution, nothing to explore
       | otherwise = maybeSolution ++ 
                             [ Explore $ g' ((h-1):is) $ S.insert (h-1) ms
                             , Explore $ g' ((h+1):is) $ S.insert (h+1) ms ] 
        where
          maybeSolution
            | S.size ms == n = [Solution is]
            | otherwise      = []

给定 n 和 m，生成要探索的子树列表。g' 是生成子树列表的辅助函数，给定已生成的 Int 列表和已使用的 Int 集。所以，有一个明确的终止条件：我们附加了一个超出所需范围的数字，或者列表变得太长 - 进一步探索无法产生解决方案，因此返回 []。否则，我们在界限内，maybeSolution 会查看 Ints 列表是否已经是一个有效的解决方案，并建议更多的子树进行探索。

    main = print $ map reverse $ generator $ g 3 6

你的问题解决了。

于 2013-08-22T17:44:44.387 回答
2

为什么使用 ++ 运算符调用 g 两次时，我得到两个 [2,1,0,1] 而不是一个？在我看来，g 中的每个结果都应该是不同的，因为在任何递归调用中，不同的数字顺序正在（或应该）累加。

但是您的 (Map,Int) 对在两个调用中是相同的，因此递归调用不知道另一个调用找到了什么。考虑调用 g ... (lastDigit-1)。它还将调用 g ... (lastDigit) （通过将 1 添加到它得到的 (lastDigit-1) ），并遵循分支 g ... (lastDigit+1) 以产生相同的结果。

此外，(Map a ()) 是 (Set a)，由于您不使用映射中的 Bool 值，因此它与 () 相同：

    import qualified Data.Set as S

    g :: Int -> Int -> Int -> Int -> (S.Set Int, Int) -> [Int] -> [[Int]]
    g n m digitCount lastDigit (hash,hashCount) digits
      | digitCount == m = if test then [reverse digits] else []
      | lastDigit < 0 || lastDigit == n  = []
      | otherwise       = g n m d' (lastDigit + 1) h' (lastDigit:digits)
                          ++ g n m d' (lastDigit - 1) h' (lastDigit:digits)
     where test = hashCount == n
           d' = digitCount + 1
           h'
            | test  = (S.empty,hashCount)
            | S.member lastDigit hash  = (hash,hashCount)
            | otherwise = (S.insert lastDigit hash,hashCount + 1)
于 2013-08-22T09:12:23.270 回答
2

g在最后一个 else 分支中结合 with的两个递归调用(++)中，您传递的参数完全相同，但lastDigit.

您的递归的基本情况不看lastDigit- 它只是比较mand digitCount，n然后hashCount返回[reverse digits]。

因此，在任何情况下，(++)case 立即被击中，然后基本 case 返回[reverse digits]，您将得到重复的相同值。

我没有完全理解您的问题说明，但也许您需要lastDigit在进行递归调用时为数字添加“新”值 - 即(lastDigit-1):digits或(lastDigit+1):digits.

于 2013-08-22T04:50:44.080 回答