Haskell generates all combinations of n numbers

Question

I am trying to create all possible combinations of n numbers. For example, if n = 3, I need 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 this for n = 3:

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

Or to avoid duplication (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, after the same template, it would very quickly become very stupid for n > 3 . Let's say I wanted to find all the combinations: (a, b, c, d, e, f, g, h, i, j) , etc.

Can someone point me in the right direction? Ideally, I would prefer not to use the built-in funtion, as I am trying to learn Haskell, and I would rather spend time understanding the code of the code, rather than just using a package written by someone else. A tuple is not required, the list will also work.

Answer 1

What are all three digit combinations? Let some of them be written by hand.

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

We finished just counting! We have listed all the numbers from 0 to 999. For an arbitrary number of digits, this generalizes directly: the upper limit is 10^n (exception), where n is the number of digits.

The rooms are specially designed in this way. It would be oddly strange if there was a possible combination of three digits that was not a real number, or if there was a three-digit number that could not be expressed by combining the three digits!

This offers a simple plan for me that simply includes arithmetic and does not require a deep understanding of Haskell *:

• Create a list of numbers from 0 to 10^n
• Turn each number into a list of numbers.

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

• Take the ratio and the remainder of your number relative to 100. Factor is the first digit of the number.
• Take the remainder from step 1 and take its coefficient and remainder with respect to 10. The factor is the second digit.
• The rest of step 2 was the third digit. This is the same as the ratio of quotient with respect to 1.

For an n-digit number, we take the factor n times, starting at 10^(n-1) and ending at 1 . Each time, we use the remainder of the last step as input to the next step. This suggests that our function, in order to turn a number into a list of digits, must be implemented as a fold: we will skip the remainder through the operation and create the list as we move. (I will leave this to you to find out how this algorithm changes if you are not in base 10!)

---

Now let's implement this idea. We want to calculate a certain number of digits, if necessary, with zero filling of a given number. What should be the type of digits ?

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

Hmm, it takes a few digits and an integer and creates a list of integers representing the digits of the input integer. The list will contain single-digit integers, each of which will have one digit from 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 is striking to me is that this code is very similar to my English description of arithmetic, which we wanted to perform. We generate a table with ten degrees due to the exposure numbers from 0 up. Then we add this table; at each step we put the factor in the list of numbers and send the remainder to the next step. We should reverse the list at the end due to the right to the left as it was built.

By the way, the template for generating a list, converting it, and then folding it back is the idiomatic thing to do in Haskell. He even had his own highest Falutin name, chylomorphism. GHC also knows about this template and can compile it into a complex cycle, optimizing the very existence of the list you are working with.

Test it out!

 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’s wrong when numberOfDigits too small for theNumber , but don’t pay attention to it.) Now we just need to create a countable list of numbers on which to use digits .

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

... and we are done!

 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 that requires a deep understanding of Haskell, see my other answer .}

Answer 2

My other answer gave an arithmetic algorithm for listing all combinations of numbers. Here is an alternative solution that arises, summarizing your example. It also works for non-numbers, because it uses only the list structure.

First, allow yourself to recall how you could use list comprehension for three-digit combinations.

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

What's going on here? Understanding the list corresponds to nested loops. z counted from 0 to 9, then y goes to 1, and z starts counting again from 0. x ticks slower. As you noticed, the list comprehension form changes (albeit in a uniform way) when you want a different number of digits. We will use this uniformity.

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

We want to abstract from the number of variables in the list comprehension (equivalently, the nesting of the loop). Let me start playing with him. First, I'm going to rewrite these lists as their equivalent monads.

 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] 

Interesting. It seems that threeDigitCombinations about the same monadic action as twoDigitCombinations , but with an additional statement. Overwriting again ...

 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) 

It should now be clear that we need to parameterize:

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

---

It works, but we are not done yet. I want to show you that this is an example of a more general monadic pattern. First, I'm going to change the implementation of combinationsOfDigits to collapse the list of constants.

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

Looking at the definition of foldUpList :: [[a]] -> [[a]] , we see that in fact it does not require the use of lists as such: it uses only monodata parts of lists. It can work on any monad, and indeed! It is located in the standard library and is called sequence :: Monad m => [ma] -> m [a] . If you are confused about this, replace m with [] and you will see that these types mean the same thing.

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

Finally, noting that sequence . replicate n sequence . replicate n is the definition of replicateM , we get it to a very fast one-line.

 combinationsOfDigits n = replicateM n [0..9] 

To summarize, replicateM n gives n-ary combinations of the input list. This works for any list, not just a list of numbers. Indeed, it works for any monad, although interpreting “combinations” only makes sense when your monad presents a choice.

This code is very concise! So much so that I think it’s not entirely obvious how this works, unlike the arithmetic version that I showed you in another answer. List monad has always been one of the monads that I find less intuitive, at least when you use higher-order monad combinators, rather than do notation.

On the other hand, it works much faster than the crunch version. On my (highly specialized) MacBook Pro compiled with -O2 , this version calculates 5-digit combinations about 4 times faster than the version that narrows the numbers. (If anyone can explain the reason for this, I'm listening!)

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 

In your case

 combos 3 [0..9]