0

I want to generate all possible combinations of a 6 element list [x1,x2,x3,x4,x5,x6] with each xi being a number between 0 and 20.

I want to generate all possible combinations of such list, apply a function (takes the list as input and outputs a magical Int) to each list, then output the results to a list of tuples. So the list of tuples looks like

[([x11,x21,x31,x41,x51,x61],Int1), ([x12,x22,x32,x42,x52,x62],Int2), ...]

I tried to this by hand by quickly realised that there are too many combinations and it is practically impossible to do by hand.

The combinations are like [0,0,0,0,0,0], [1,7,0,10,11,6], [7,7,7,7,6,6], [20,20,20,20,20,20] and so on.

I know how to generate all combinations of a list and put them in a list of lists (because I asked this before)

foo [] = [[]]
foo (x:xs) = foo xs ++ map (x:) (foo xs)

What I want to achieve this time is different because I am not trying to generate the different combinations within a particular list, I am trying to generate all 6 element lists.

user6005857
  • 631
  • 9
  • 25
  • There are only 64000000 (20^6) of them, how is that "too many"? You probably should use a more clever approach to your actual problem. What are these magical ints, what are you doing with them, and why do you need so many? – Bergi May 13 '16 at 02:07
  • I think you'll find the examples on the Haskell wiki page on [List Comprehensions](https://wiki.haskell.org/List_comprehension) helpful. – ErikR May 13 '16 at 02:13
  • @Bergi If you actually read the surrounding context, it's too many to process *by hand*. – user253751 May 13 '16 at 03:21
  • @immibis, it probably was sarcasm. 20⁶ is quite a lot, and in many cases you don't actually need that It's impossible to tell without knowing the actual problem though. – lierdakil May 13 '16 at 05:05

2 Answers2

3

As far as I can tell, you want a cartesian product (denoted by × here) of 6 lists [0..20].

So essentially, something like this:

[0..20]×[0..20]×[0..20]×[0..20]×[0..20]×[0..20]

That's a lot of elements (85,766,121 to be exact). But, it could be done.

Perhaps an easier to understand version is as follows.

Let us define a function, cart, that would do something like a cartesian product over a list and a list of lists:

let cart xs ls = [x:l | x <- xs, l <- ls]

This function will take all elements from xs, and all elements from ls and build a list of lists with all possible concatenations.

Now, we need a base case. Suppose you wanted a list of lists of a single element instead of six. How would you apply our cart function? Well, since it adds each element from first argument to every element in second argument, we can pass a list of a single empty list as a second argument, and [0..20] as first argument:

cart [0..20] [[]]

We get

[[0],[1],[2],[3],[4],[5],[6],[7],[8],[9],[10],[11],[12],[13],[14],[15],[16],[17],[18],[19],[20]]

Great. Now we just apply it 6 times to its own result, starting with [[]]:

foldr ($) [[]] $ replicate 6 (cart [0..20])

($) is function application.

replicateM from Control.Monad (defined as sequence of n monadic actions: replicateM n x = sequence (replicate n x)) basically does the same when applied to lists (see e.g. Why does application of `sequence` on List of Lists lead to computation of its Cartesian Product? for why exactly that is) So shorter answer would be like this:

replicateM 6 [0..20]

You can map over those after this, e.g.

map (\x -> (x, magicFunction x)) $ replicateM 6 [0..20]
Community
  • 1
  • 1
lierdakil
  • 548
  • 2
  • 9
1

foo f xs = map (\ys -> (ys,f ys)) (replicateM (length xs) xs)

Here replicateM (length xs) xs will generate all combinations of the elements in xs. Then you just map over it.

Results in GHCI:

>import Control.Monad
>let foo f xs = map (\ys -> (ys,f ys)) (replicateM (length xs) xs)
>foo sum [1,2]
[([1,1],2),([1,2],3),([2,1],3),([2,2],4)]
liminalisht
  • 1,243
  • 9
  • 11
Free_D
  • 577
  • 3
  • 16