Haskell生成n个数字的所有组合 [英] Haskell generating all combinations of n numbers

问题描述

我正在尝试生成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;在[（a，b，c）|中m < -  [0..3 * 1]，
a < -  [0..1]，b < -  [0..1]，c < -  [0..1]，
 + b + c == m] 
  

然而，遵循相同的模式会变得非常愚蠢快速为 n> 3 。假设我想找到所有的组合：（a，b，c，d，e，f，g，h，i，j）等。

任何人都可以在这里指出正确的方向吗？理想情况下，我宁愿不使用内置函数，因为我正在尝试学习Haskell，我宁愿花时间理解代码，而不愿意使用其他人写的包。一个元组不是必需的，列表也是可行的。

解决方案

三个数字的所有组合是什么？我们手动写出几张。

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

我们只是简单的计数！我们列举了0到999之间的所有数字。对于任意数字的数字，这个概括直接表示为：上限为 10 ^ n （独占），其中 n 是数字的位数。

数字是故意设计的。如果可能的三位数字组合不是有效的数字，或者如果有三位数字不能通过组合三位数字来表示，那将会很奇怪！

这为我提供了一个简单的计划，它只涉及算术，并且不需要对Haskell *有深入的理解：

1. 生成0到 10 ^ n


2. 中的数字列表将每个数字转换为数字列表。
>

第2步是有趣的部分。要提取三位数字的数字（以10为底数），请你做这个：

1. 取商数和商数的余数为100。数字。


2. 取第1步的余数，并取其10的商数和余数。商是第2位数。


3. 第二步的余数是第三位。这与将商数取为1相同。
   




对于 n -digit数字，我们以 10 ^（n-1）开头并以 n 次> 1 。每一次，我们使用上一步的余数作为下一步的输入。这表明我们将数字转换为数字列表的功能应该作为一个折叠来实现：我们将通过操作对剩下的部分进行线程化，并随时建立一个列表。 （如果你不在10的基础上，我会让你知道这个算法是如何改变的！）





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

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

嗯，它需要一些数字和一个整数，并产生一个列表代表输入整数数字的整数。该列表将包含一位数字的整数，每一个整数将是输入数字的一位数字。

 位数numberOfDigits theNumber = （位数，余数）= 
 let（digit，newRemainder）=余数`divMod`指数
 in（digit：数字，newRemainder）
 powersOfTen = [10 ^ n | n<  -  [0 ..（numberOfDigits-1）]] 
  

这段代码看起来和我们想要执行的算术的英文描述非常相似。我们通过从0开始的数字取幂来生成一个10的幂次表。然后我们把那张桌子折叠起来。在每一步中，我们将商放在数字列表中，并将余数发送到下一步。我们必须 reverse 结尾处的输出列表，因为它是从右向左的方式构建的。





顺便说一句，生成一个列表，转换它，然后折叠它的模式在Haskell中是一个惯用的事情。它甚至有它自己的高衰落'的数学名称， hylomorphism 。 GHC也知道这种模式并且可以将它编译成一个紧密的循环，优化你正在使用的列表的存在。





让我们来测试它！

  ghci>数字3 123 
 [1，2，3] 
 ghci>数字5 10101 
 [1,0,1,0,1] 
 ghci>数字6 99 
 [0,0,0,0,9,9] 
  

它奇迹般有效！ （好吧，当 numberOfDigits 对于 theNumber 而言太小了，但是不用担心。）现在我们只需要生成一个数字清单，用于使用 digits 。

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

......并且我们已经完成了！



  ghci> combinationOfDigits 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 ，请参阅我的其他答案。}




I am trying to generate all possible combinations of n numbers. For example if n = 3 I would want the following combinations:

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

This post describes how to do so for n = 3:

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

Or to avoid duplicates (i.e. multiple copies of the same 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 ]

However following the same pattern would become very silly very quickly for n > 3. Say I wanted to find all of the combinations: (a, b, c, d, e, f, g, h, i, j), etc.

Can anyone point me in the right direction here? Ideally I'd rather not use a built in funtion as I am trying to learn Haskell and I would rather take the time to understand a peice of code than just use a package written by someone else. A tuple is not required, a list would also work.

解决方案

What are all the combinations of three digits? Let's write a few out manually.

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

We ended up simply counting! We enumerated all the numbers between 0 and 999. For an arbitrary number of digits this generalises straightforwardly: the upper limit is 10^n (exclusive), where n is the number of digits.

Numbers are designed this way on purpose. It would be jolly strange if there was a possible combination of three digits which wasn't a valid number, or if there was a three-digit number which couldn't be expressed by combining three digits!

This suggests a simple plan to me, which just involves arithmetic and doesn't require a deep understanding of Haskell*:

1. Generate a list of numbers between 0 and 10^n
2. Turn each number into a list of digits.

Step 2 is the fun part. To extract the digits (in base 10) of a three-digit number, you do this:

1. Take the quotient and remainder of your number with respect to 100. The quotient is the first digit of the number.
2. Take the remainder from step 1 and take its quotient and remainder with respect to 10. The quotient is the second digit.
3. The remainder from step 2 was the third digit. This is the same as taking the quotient with respect to 1.

For an n-digit number, we take the quotient n times, starting with 10^(n-1) and ending with 1. Each time, we use the remainder from the last step as the input to the next step. This suggests that our function to turn a number into a list of digits should be implemented as a fold: we'll thread the remainder through the operation and build a list as we go. (I'll leave it to you to figure out how this algorithm changes if you're not in base 10!)

---

Now let's implement that idea. We want calculate a specified number of digits, zero-padding when necessary, of a given number. What should the type of digits be?

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

Hmm, it takes in a number of digits and an integer, and produces a list of integers representing the digits of the input integer. The list will contain single-digit integers, each one of which will be one digit of the input number.

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)]]

What's striking to me is that this code looks quite similar to my English description of the arithmetic we wanted to perform. We generate a powers-of-ten table by exponentiating numbers from 0 upwards. Then we fold that table back up; at each step we put the quotient on the list of digits and send the remainder to the next step. We have to reverse the output list at the end because of the right-to-left way it got built.

By the way, the pattern of generating a list, transforming it, and then folding it back up is an idiomatic thing to do in Haskell. It's even got its own high-falutin' mathsy name, hylomorphism. GHC knows about this pattern too and can compile it into a tight loop, optimising away the very existence of the list you're working with.

Let's test it!

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]

It works like a charm! (Well, it misbehaves when numberOfDigits is too small for theNumber, but never mind about that.) Now we just have to generate a counting list of numbers on which to use digits.

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

... and we've finished!

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]]

_{* For a version which does require a deep understanding of Haskell, see my other answer.}

这篇关于Haskell生成n个数字的所有组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！