Generating all possible combinations of numbers in

Question

Say for example I want to construct a triplet, taking in every combination of numbers from 1..100 in a triplet; i.e:

[(0,0,0),(0,0,1),(0,1,1),(1,1,1),(0,0,2),(0,1,2),(0,2,2),(1,2,2)]

..etc etc, up until a given bound (i.e: 100: giving us a final triplet of (100,100,100)); is there any reasonable way of doing this within haskell, or would I be best off writing a method that in short held a boundary pointer, and recursively increased each number until it was equal to the number to its right?

Answer 1

I think your description best fits a list comprehension to express what you want to do:

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

Answer 2

You say you want the numbers 1..100, but mention 0 in the examples. Further, you say "every combination" but then do not mention (1,0,0).

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

to avoid duplicates, enumerate them in the order of their total sum:

let l = 100; in [(a,b,c) | m<-[0..3*l],
                           a<-[0..l], b<-[0..l], c<-[0..l],
                           a+b+c == m ]

The calculation can be accelerated (by keeping the same result), by narrowing down the possible ranges:

let l = 100; in [(a,b,m-a-b) | m<-[0..3*l],
                               a<-[(max 0 (m-2*l))..(min l m)],
                               b<-[(max 0 (m-a-l))..(min l (m-a))] ]