在Haskell中生成笛卡尔积

Question

我将尝试生成n个数字的所有可能组合。例如，如果n = 3，则我希望得到以下组合：

(0,0,0), (0,0,1), (0,0,2)... (0,0,9), (0,1,0)... (9,9,9).

这篇文章讲述了如何为n = 3生成所有可能的数字组合：

[(a,b,c) | m <- [0..9], a <- [0..m], b <- [0..m], c <- [0..m] ]

为避免重复（即同一n-uple的多个副本）：

let l = 9; in [(a,b,c) | m <- [0..3*l],
                         a <- [0..l], b <- [0..l], c <- [0..l],
                         a + b + c == m ]

然而，对于n > 3，按照相同的模式很快就会变得非常愚蠢。比如说，我想找到所有组合：(a, b, c, d, e, f, g, h, i, j)等。

有人可以指点我方向吗？理想情况下，我不想使用内置函数，因为我正在尝试学习Haskell，我宁愿花时间理解一段代码，而不是只使用其他人编写的包。元组不是必需的，列表也可以。

- James Allingham

---

请编写一个递归函数。给定 n-1 种选择的组合，生成 n 种选择的组合。您需要输出一个列表，而不是一个固定长度的元组。 - chi

如果你解决了这个问题后仍想利用库函数，那么知道replicateM n [1..100]可以完成任务。不过，要意识到为什么它能够实现并不是一个简单的练习，所以最好在更熟悉Haskell后再进行尝试。 - chi

sequence $ replicate 3 [0..9] 将生成一个列表的笛卡尔积，而不是元组，但很容易推广。 - karakfa

生成所有数字的组合...例如，对于3位数，它将是000，001，002... 009，010，011... 999...我是否遗漏了什么，或者这不是数学概念中所称的计数？ - Mark Seemann

为什么没有人提到这个问题与组合完全无关。 - Redu

Answer 1

我的另一个答案给出了一个算法来枚举所有数字的组合。这里有一个替代方案，通过推广您的示例而产生。它也适用于非数字，因为它只使用列表的结构。

首先，让我们回想一下如何使用列表推导式来获取三位数的组合。

threeDigitCombinations = [[x, y, z] | x <- [0..9], y <- [0..9], z <- [0..9]]

这里发生了什么？列表推导式对应嵌套循环。 z 从0到9计数，然后y增加到1，z再次开始计数。 x的速度最慢。正如您所注意到的那样，当您需要不同数量的数字时，列表推导式的形状会发生变化（尽管以统一的方式）。我们将利用这种一致性。

twoDigitCombinations = [[x, y] | x <- [0..9], y <- [0..9]]

我们希望在列表推导式中抽象出变量的数量（同样地，循环的嵌套）。让我们开始尝试一下。首先，我将把这些列表推导式重写为它们等效的单子推导式。

threeDigitCombinations = do
    x <- [0..9]
    y <- [0..9]
    z <- [0..9]
    return [x, y, z]
twoDigitCombinations = do
    x <- [0..9]
    y <- [0..9]
    return [x, y]

有趣。看起来 threeDigitCombinations 大致上与 twoDigitCombinations 相同，只是多了一个语句。重新编写...

zeroDigitCombinations = [[]]  -- equivalently, `return []`
oneDigitCombinations = do
    z <- [0..9]
    empty <- zeroDigitCombinations
    return (z : empty)
twoDigitCombinations = do
    y <- [0..9]
    z <- oneDigitCombinations
    return (y : z)
threeDigitCombinations = do
    x <- [0..9]
    yz <- twoDigitCombinations
    return (x : yz)

现在我们应该清楚需要参数化的内容了：

combinationsOfDigits 0 = return []
combinationsOfDigits n = do
    x <- [0..9]
    xs <- combinationsOfDigits (n - 1)
    return (x : xs)

ghci> combinationsOfDigits' 2
[[0,0],[0,1],[0,2],[0,3],[0,4],[0,5],[0,6],[0,7],[0,8],[0,9],[1,0],[1,1] ... [9,8],[9,9]]

---

代码运行成功了，但我们还没有完成。我想向您展示这是更一般的单子模式实例。首先，我将更改combinationsOfDigits的实现方式，使其折叠常量列表。

combinationsOfDigits n = foldUpList $ replicate n [0..9]
    where foldUpList [] = return []
          foldUpList (xs : xss) = do
              x <- xs
              ys <- foldUpList xss
              return (x : ys)

看一下 foldUpList :: [[a]] -> [[a]] 的定义，我们可以发现它实际上并不需要使用 列表：它只使用了列表的 monad-y 部分。它可以在任何 monad 上运行，并且确实如此！它在标准库中，名为 sequence :: Monad m => [m a] -> m [a]。如果您对此感到困惑，请将 m 替换为 []，您应该能够看出这些类型是相同的。

combinationsOfDigits n = sequence $ replicate n [0..9]

最后，注意到 sequence . replicate n 是replicateM的定义，我们把它改为一个简洁的单行代码。

combinationsOfDigits n = replicateM n [0..9]

总之，replicateM n 会给出输入列表的n元组合。这适用于任何列表，而不仅限于数字列表。实际上，它适用于任何单子-尽管“组合”解释只有在你的单子表示选择时才有意义。

这段代码非常简洁！甚至我认为它的工作原理并不完全明显，与我在另一个答案中展示的算术版本不同。列表单子一直是我觉得不太直观的单子之一，至少当你使用高阶单子组合器而不是do符号时是如此。

另一方面，它比数字计算版本运行得要快得多。在我的（高规格）MacBook Pro上，使用-O2编译，这个版本计算五位数字组合的速度比数字计算版本快4倍左右。（如果有人能解释这个原因，我在听！）

- Benjamin Hodgson

---

这个答案和第一个答案一样有效吗？看起来应该是的，尽管我对 GHC 的优化能力不是特别熟悉。 - ThreeFx

好问题，我不知道答案。今天晚些时候有时间时，我会进行基准测试并更新帖子。 - Benjamin Hodgson

Answer 2

三位数的所有组合是什么？让我们手动写出一些。

000, 001, 002 ... 009, 010, 011 ... 099, 100, 101 ... 998, 999

我们最终只是进行了简单的“计数”！我们枚举了0到999之间的所有数字。对于任意数量位数的数字，这个方法很容易地推广开来：上限为10^n（不包括），其中n是位数。

数字是有意设计成这样的。如果存在三个数字的组合不是有效数字，或者存在低于1000的数字无法通过组合三个数字来表示，那将会非常奇怪！

这启示我一个简单的方案，只涉及算术，不需要对Haskell有深入的理解：

1. 生成0到10^n之间的数字列表
2. 将每个数字转换为数字列表

步骤2是有趣的部分。要提取三位数字的（十进制）数字，请按照以下方式操作：

1. 将数与100取商和余数。商是该数的第一位数字。
2. 用步骤1的余数对10取商和余数。商是第二个数字。
3. 步骤2的余数就是第三个数字。这与对1取商相同。

对于一个n位数，我们需要取商n次，从10^(n-1)开始，以1结束。每次，我们使用上一步的余数作为下一步的输入。这表明将数字转换为数字列表的函数应该实现为一个fold：我们将余数通过操作线程，并在进行的过程中构建一个列表。（如果您不是在10进制中，我会让您自己想出如何改变算法！）

---

现在让我们实现这个想法。我们希望计算给定数字的指定位数，并在必要时进行零填充。 digits 的类型应该是什么？

digits :: Int -> Int -> [Int]

这个函数接收一个数字和一个整数，然后生成一个整数列表来表示输入整数的各位数字。该列表将包含单个数字整数，每个整数都是输入数字的一位。

digits numberOfDigits theNumber = reverse $ fst $ foldr step ([], theNumber) powersOfTen
    where step exponent (digits, remainder) =
              let (digit, newRemainder) = remainder `divMod` exponent
              in (digit : digits, newRemainder)
          powersOfTen = [10^n | n <- [0..(numberOfDigits-1)]]

我觉得引人注目的是，这段代码看起来与我对所需执行的算术的英文描述非常相似。我们通过将数字从0开始进行指数运算来生成十的幂表。然后我们将该表折叠回去；在每个步骤中，我们将商放在数字列表中，并将余数发送到下一步。由于它的右到左的构建方式，我们必须在最后reverse输出列表。

顺便说一下，在Haskell中，生成列表、转换列表，然后将其折叠回去的模式是一种惯用的做法。它甚至有自己高大上的数学名字，称为。 GHC也知道这种模式，可以将其编译成紧凑的循环，优化掉您正在使用的列表的存在。

让我们来测试一下！

ghci> digits 3 123
[1, 2, 3]
ghci> digits 5 10101
[1, 0, 1, 0, 1]
ghci> digits 6 99
[0, 0, 0, 0, 9, 9]

它像魔法一样运行！（好吧，当numberOfDigits对于theNumber来说太小时，它会表现不良，但是不用担心。）现在我们只需要生成一个数字计数列表，然后使用digits。

combinationsOfDigits :: Int -> [[Int]]
combinationsOfDigits numberOfDigits = map (digits numberOfDigits) [0..(10^numberOfDigits)-1]

...并且我们完成了！

ghci> combinationsOfDigits 2
[[0,0],[0,1],[0,2],[0,3],[0,4],[0,5],[0,6],[0,7],[0,8],[0,9],[1,0],[1,1] ... [9,7],[9,8],[9,9]]

_{* 如果需要深入了解Haskell的版本，请参见我的其他答案。}

- Benjamin Hodgson

---

这是一篇非常棒的文章！Haskell 不断地让我惊叹！你有什么教程可以推荐吗？正如你所指出的，这个答案比你的第二个答案更容易理解，虽然我认为我能够理解这个答案，但我只是浅尝辄止。它非常令人望而生畏！然而，看到你的解决方案如此巧妙地与标准库相结合，真是太酷了！如果我可以接受两个答案，我会的！ - James Allingham

谢谢！很高兴能帮忙。关于教程，你可能已经读过了，但是《Learn You A Haskell》仍然是我读过的最好的编程书籍之一。它有趣易懂，对于更高级的主题也解释得非常好。顺便说一下，如果你对其他答案中的任何内容不理解，我很乐意详细解释。 - Benjamin Hodgson

Answer 3

combos 1 list = map (\x -> [x]) list
combos n list = foldl (++) [] $ map (\x -> map (\y -> x:y) nxt) list
    where nxt = combos (n-1) list

在您的情况下

combos 3 [0..9]

- Ilya Prokin