1

So for a project, I have to create, as said a list of lists of all combinations from 0 to 9 but is limited to a list of 6 numbers. So that the result looks something like this:

Solutions ==> [[0,0,0,0,0,0], [0,0,0,0,0,1], ... [9,9,9,9,9,9]]

Thanks

elias_0404
  • 21
  • 4
  • 5
    You are misusing the word "permutation", which means a re*ordering*. What you are looking for is called a "cartesian product". – luqui Oct 27 '20 at 15:34
  • [A permutation of _n_ elements still has every and only those _n_ elements](https://en.wikipedia.org/wiki/Permutation). Yours are not permutations. – Enlico Oct 27 '20 at 15:35
  • 2
    [`mapM (const [0..9]) [1..6]`](https://stackoverflow.com/a/64541430/849891) == `replicateM 6 [0..9]`. – Will Ness Oct 27 '20 at 16:15
  • If you are just looking for the Cartesian product of six times [0..9], that is allowing repetitions, you could look at the “note on efficiency” here: [SO_q63452618](https://stackoverflow.com/a/63452618/11282404). The code there is basically like `replicateM` but can be far less memory intensive. – jpmarinier Oct 28 '20 at 11:48
  • Thanks guys just what I was looking for, sorry for the misuse of permutations, reading over it a day later made me see my error. – elias_0404 Oct 29 '20 at 12:31

3 Answers3

1

Check it out:

ghci> [ [x,y] | x <- [1..3], y <- [1..3] ]
[[1,1],[1,2],[1,3],[2,1],[2,2],[2,3],[3,1],[3,2],[3,3]]

Your move.

luqui
  • 59,485
  • 12
  • 145
  • 204
1

First of all, what your asking about is not a list of permutations but a list of all possible combinations. In a permutation each digit would appear only once.

Basing on the example you gave one can write a recursive function, generating all combinations for lists of n elements:

combinationsMaker n = if n == 1 then [[digit] | digit <- [0..9]] else [sublist ++ [digit] | digit <- [0..9], sublist <- combinationsMaker (n-1)]

My Haskell is quite rusty, so it might not be the most idiomatic. Possibly one would like to factor out the allowed elements, so its not only all digits.

Max Görner
  • 674
  • 7
  • 16
1

The text of your question seem to imply that you want to get all possibilities, with digit repetitions allowed and reordered versions being regarded as distinct. That is, you want the Cartesian product of 6 times [0..9].

If so, you are led to expect 106 = 1 million possibilities. As mentioned in the comment by Will Ness, you can use either mapM (const [0..9]) [1..6] or the equivalent expression replicateM 6 [0..9].

Checking under the ghci interpreter:

 λ> 
 λ> import Control.Monad (replicateM)
 λ> 
 λ> length $ mapM (const [0..9]) [1..6]
 1000000
 λ> 
 λ> length $ replicateM 6 [0..9]
 1000000
 λ> 
 λ> length $ sequence (replicate 6 [0..9])
 1000000
 λ> 
 λ> replicateM 6 [0..9] == sequence (replicate 6 [0..9])
 True
 λ>

However, there is a performance caveat.

Library function replicateM is highly polymorphic. Acting as the list cartesian product is not its sole role in life. Unfortunately, this happens to have the sad side effect that its peak memory consumption can become quite large (exponentially large) if you go beyond toy-sized examples.

Fortunately, there is a known workaround based on an idea by K. A. Buhr:

cartesianProduct :: [[α]] -> [[α]]
cartesianProduct xss =
    map reverse (helper (reverse xss))
        where
            helper :: [[α]] -> [[α]]
            helper [] = [[]]
            helper (ys:zss) = [y:zs | zs <- helper zss, y <- ys]

Checking:

 λ> 
 λ> length $ cartesianProduct (replicate 6 [0..9])
 1000000
 λ> 
 λ> cartesianProduct (replicate 6 [0..9]) == replicateM 6 [0..9]
 True
 λ>

Alternatively, let's now assume you do need actual combinations. That is, you no longer allow repeated digits, and you want to regard [1,2,3,4,5,6] as identical to [6,5,4,3,2,1]. The number of possibilities thus becomes much smaller.

In such a case, you can use a more restrictive version of the code for cartesianProduct:

combis :: Ord α => Int -> [α] -> [[α]]
combis k xs =
    let  xss = replicate k xs
         helper1 :: [[α]] -> [[α]]
         helper1 [] = [[]]
         helper1 (ys:zss) = [y:zs | zs <- helper1 zss, y <- ys,
                                    (null zs) || (head zs < y)]
    in
        map reverse (helper1 xss)

Checking:

 λ> 
 λ> cb = combis 6 [0..9]
 λ> length cb
 210
 λ> div (10*9*8*7*6*5) (6*5*4*3*2*1)
 210
 λ> take 10 cb
 [[0,1,2,3,4,5],[0,1,2,3,4,6],[0,1,2,3,4,7],[0,1,2,3,4,8],[0,1,2,3,4,9],[0,1,2,3,5,6],[0,1,2,3,5,7],[0,1,2,3,5,8],[0,1,2,3,5,9],[0,1,2,3,6,7]]
 λ>
jpmarinier
  • 4,427
  • 1
  • 10
  • 23