9

我想做一个方法，我可以给它一个长度列表，它会返回笛卡尔坐标的所有组合，直到这些长度。用一个例子更容易解释：

cart [2,5]
Prelude> [ [0,0],[0,1],[0,2],[0,3],[0,4],[1,0],[1,1],[1,2],[1,3],[1,4] ]

cart [2,2,2]
Prelude> [ [0,0,0],[0,0,1],[0,1,0],[0,1,1],[1,0,0],[1,0,1],[1,1,0],[1,1,1] ]

一个简单的列表理解是行不通的，因为我不知道列表会有多长。虽然我喜欢 Haskell 对许多问题的简单性，但这是我可以在 5 分钟内以程序方式（用 C 或其他东西）编写的问题，而 Haskell 给了我一个动脉瘤！

解决这个特定问题会对我有很大帮助；我也很想听听您在处理此类问题时的思维过程。

4

3 回答 3

13

嗯..

cart = sequence . map (enumFromTo 0 . subtract 1)

[[a]] -> [[a]]期望库中已经存在执行我们期望的函数是合理的。因此，如果一个人不熟悉sequence，找到它是一件简单的事情。

编辑：正如 newacct 指出的那样：

cart = mapM (enumFromTo 0 . subtract 1)

这也可以通过将先前的解决方案提供给HLint来找到。

于 2010-04-11T09:32:27.610 回答
12

这可以递归解决。首先，无的笛卡尔积是 {∅}：

cart [] = [[]]

（或者如果空产品无效，则仅定义 1 元素形式：

cart [x] = [[i] | i <- [0 .. x-1]]

)

那么， 的笛卡尔积x:xs可以写成

cart (x:xs) = [i:rest | i <- [0 .. x-1], rest <- cart xs]

一般来说，如果你要编写一个需要列表长度N的函数f，试着想办法让f(N)只依赖于较小的列表，例如f(N - 1)，然后解决基本情况f( 0)或f(1)等。这将问题转换为可以轻松解决的递归。

于 2010-04-11T07:46:18.417 回答
7

我敢打赌，您的程序解决方案将涉及递归。我们的 Haskell 解决方案也将涉及递归。

所以，递归。首先是递归情况。

cart (c : cs) = [i : r | i <- [0 .. c-1], r <- rcart]
  where rcart = cart cs

在这里，我们只是说对于每个可能的初始坐标，以及来自剩余长度的笛卡尔坐标的每个可能组合，我们要做的显而易见的事情是将坐标与剩余坐标结合起来。

然后是基本情况。

cart [] = [[]]

你可能会想cart [] = []。我一开始也是。但是考虑一下递归案例对基本案例的要求。

于 2010-04-11T07:50:16.960 回答