[Tutor] Combination

[Danny Yoo]

On Fri, 21 Jan 2005, Guillermo Fernandez Castellanos wrote:

> I'm trying to take a list and find all the unique combinations of that
> list.
>
> I mean:
> if I enter (1,2,3,4,5) and I watn combinations of 3, I want to find:
> (1,2,3) but then not (2,1,3), (3,1,2),...
> (1,2,4)
> (1,2,5)
> (2,3,5)
> (3,4,5)


Hi Guillermo,


There is a clean recursive way to define this.  I'll try to sketch out how
one can go about deriving the function you're thinking of.


Let's say that we have a list L,

     [1, 2, 3]

and we want to create all combinations of elements in that list.  Let's
call the function that does this "createComb()".  How do we calculate
createComb([1, 2, 3])?


We can just start writing it out, but let's try a slightly different
approach.  Imagine for the moment that we can construct createComb([2,
3]):

    createComb([2, 3])   -> [[2, 3], [2], [3]]


We know, just from doing things by hand, that createComb([1, 2, 3]) of the
whole list will look like:

    createComb([1, 2, 3) -> [[1, 2, 3], [1, 2], [1, 3],
                                [2, 3],    [2],    [3]]

If we compare createComb([1, 2, 3]) and createComb([2, 3]), we might be
able to see that they're actually very similar to each other.


Does this make sense so far?  Please feel free to ask questions about
this.



Good luck!