Haskell生成n个数的所有组合

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,我宁愿花时间去理解一些代码而不仅仅是使用其他人编写的包.不需要元组,列表也可以.

Answer 1

三位数的所有组合是什么？我们手动写几个.

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

我们最终还算数!我们列举了0到999之间的所有数字.对于任意数字的数字,这直截了当地说明:上限是10^n(不包括),其中n是数字位数.

数字是故意这样设计的.如果有三个数字的可能组合不是有效数字,或者如果有一个三位数的数字无法用三位数组合表示,那将是非常奇怪的!

这对我来说是一个简单的计划,它只涉及算术,不需要深入理解Haskell*:

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

第2步是有趣的部分.要提取三位数字的数字(在基数10中),请执行以下操作:

1. 取数字的商和余数相对于100.商是数字的第一个数字.
2. 从第1步取余数,取其商和余数相对于10.商是第二位数.
3. 第2步的其余部分是第三位数.这与取1的商相同.

对于n位数,我们采用商n,从开始到10^(n-1)结束1.每次,我们使用最后一步的余数作为下一步的输入.这表明我们将数字转换为数字列表的函数应该实现为折叠:我们将通过操作线程化其余部分并构建一个列表.(如果你不在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中惯用的事情.它甚至有自己的高f'数字名称,hylomorphism.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]]

_{*对于一个版本,它确实需要哈斯克尔的深刻理解,看到我的其他答案.}

Answer 2

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

首先,让我们提醒自己如何使用列表理解来实现三位数组合.

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

这里发生了什么？列表推导对应于嵌套循环.z计数从0到9,然后y上升到1并z再次从0开始计数.x滴答最慢.如您所知,当您需要不同数量的数字时,列表推导的形状会发生变化(尽管是统一的).我们将利用这种一致性.

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

我们想要抽象列表推导中的变量数量(等效地,循环的嵌套).让我们开始玩吧.首先,我将把这些列表推导重写为等效的monad理解.

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大致相同的monadic动作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]]

它有效,但我们还没有完成.我想告诉你,这是一个更一般的monadic模式的实例.首先,我要更改实现,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个组合.这适用于任何列表,而不仅仅是数字列表.事实上,它适用于任何monad - 虽然"组合"解释只有在你的monad代表选择时才有意义.

这段代码确实非常简洁!因此,我认为它的工作方式并不完全明显,这与我在其他答案中向您展示的算术版本不同.列表monad一直是我发现不太直观的monad之一,至少当你使用高阶monad组合器而不是do-not时.

另一方面,它比数字运算版本运行得快得多.在我的(高规格)MacBook Pro上编译时-O2,这个版本计算的5位数组合比压缩数字的版本快4倍.(如果有人能解释我正在听的原因!)