Finding combinations

Question

I want to write a function which calculates all combinations of the numbers 1 to 7 in 7-tuples, but every number can occur only once in every tuple.

So far I found this approach, but it also returns combinations with multiple occurrences of the same number in every tuple. I am not quite sure how to remove tuples with multiple occurrences of the same number.

  a = [(a,b,c,d,e,f,g) | a <- [1..7], b <- [1..7], c <- [1..7], 
        d <- [1..7], e <- [1..7], f <- [1..7], g <- [1..7]]

Example for goal result (all valid combinations should be in here):

  [(1,2,3,4,5,6,7),(2,1,3,4,5,6,7),(2,3,1,4,5,6,7),...]

Answer 1

You can use list difference (\\) from Data.List.

perms = [ (a,b,c,d,e,f,g) | a <- [1..7]
                          , b <- [1..7] \\ [a]
                          , c <- [1..7] \\ [a,b]
                          , d <- [1..7] \\ [a,b,c]
                          , e <- [1..7] \\ [a,b,c,d]
                          , f <- [1..7] \\ [a,b,c,d,e]
                          , g <- [1..7] \\ [a,b,c,d,e,f] ]

This way b will be chosen to be different from a, c will be different from a and b, and so on.

Answer 2

We can optimize the code from the answer by kuoytfouy, as

perms = [(a,b,c,d,e,f,g) | a <- [1..7], let dom6 = [1..7] \\ [a]
                         , b <- dom6,   let dom5 = dom6 \\ [b]
                         , c <- dom5,   let dom4 = dom5 \\ [c]
                         , d <- dom4,   let dom3 = dom4 \\ [d] 
                         , e <- dom3,   let dom2 = dom3 \\ [e] 
                         , f <- dom2,   let dom1 = dom2 \\ [f] 
                         , g <- dom1,   let dom0 = dom1 \\ [g]  ]

and further improve it by cutting away the redundant computations,

perms = [(a,b,c,d,e,f,g) | a <- [1..7], let dom6 = delete a [1..7]
                         , b <- dom6,   let dom5 = delete b dom6
                         , c <- dom5,   let dom4 = delete c dom5
                         , d <- dom4,   let dom3 = delete d dom4 
                         , e <- dom3,   let dom2 = delete e dom3 
                         , f <- dom2,   let [g]  = delete f dom2 ]

Composing the choosing of an element with its deletion from the current domain gives us one function that does the two jobs at the same time, usually called picks. It's been used in SO answers in the past and can be found there.

See also:

• picks from one pigworker
• choose in Unique Selection monad
• a Common Lisp answer of mine with an efficient code which actually shrinks the domain list by surgical mutation of the list structure, plucking the elements out one by one as we go down the recursively built nested loops; and healing it on the way back.
  That is to say, choose- (or equivalently, picks-) based Haskell code is under grave suspicion of being grossly inefficient (inits being quadratic when fully forced, for starters).
  Re-calculating the shrunk domains each time, like in this answer, we only end up with seven (six, whatever) domain lists at each point in time, each fully garbage collectible when done with -- but, each delete invocation searches its argument from the start anew (the inefficiency picks was invented to fix...), again suggesting the overall calculation being quadratic, inefficient. Food for thought!

Answer 3

What about something like:

import Data.List
list = [(a,b,c,d,e,f,g) | a <- [1..7], b <- [1..7], c <- [1..7],
        d <- [1..7], e <- [1..7], f <- [1..7], g <- [1..7], [1,2,3,4,5,6,7]\\[a,b,c,d,e,f,g]==[]]

Answer 4

We can make a "helper function" here that for a given list xs generates a list of tuples where the first element is an element we picked, and the second the list of remaining elements, like:

import Data.List(inits, tails)

pick :: [a] -> [(a, [a])]
pick ls = [(b, as ++ bs) | (as, (b:bs)) <- zip (inits ls) (tails ls)]

For example:

Prelude Data.List> pick [1..5]
[(1,[2,3,4,5]),(2,[1,3,4,5]),(3,[1,2,4,5]),(4,[1,2,3,5]),(5,[1,2,3,4])]

each item thus picks an element from the list and returns a list where that picked element is removed. We can use this to then pass that list to the next generator.

Then we can use this for example in a do block like:

perms :: (Num a, Enum a) => [(a, a, a, a, a, a, a)]
perms = do
    (a, as) <- pick [1..7]
    (b, bs) <- pick as
    (c, cs) <- pick bs
    (d, ds) <- pick cs
    (e, es) <- pick ds
    (f, [g]) <- pick es
    return (a, b, c, d, e, f, g)

which yields:

Prelude Data.List> perms
[(1,2,3,4,5,6,7),(1,2,3,4,5,7,6),(1,2,3,4,6,5,7),(1,2,3,4,6,7,5),(1,2,3,4,7,5,6),(1,2,3,4,7,6,5),(1,2,3,5,4,6,7),(1,2,3,5,4,7,6), ...