[Tutor] Recursive combinations?

[Remco Gerlich]

On  0, Andrew Wilkins <toodles@yifan.net> wrote:
> I'm trying to make combinations of 2 out of a set {1,2,3,...,n}
> I can do it for a predefined set where n=10 using the following:
> 
> part1=[]
> 
> for a in range(1,11):
> 	for b in range(a+1,11):
> 		part1.append((a,b))
> 
> Is there some way I can make a recursive function so this combination
> function can be extended where the amount of items in a combination could be
> larger? For example for 3 items I'd just add another nested loop:
> 
> part1=[]
> 
> for a in range(1,11):
> 	for b in range(a+1,11):
> 		for c in range(b+1,11)
> 			part1.append((a,b,c))
> 
> There's an obvious pattern, so that's why I thought of recursion. However I
> can't seem to get my head around recursion, even after going through and
> understanding Alan Gauld's tutorial on it.
> 
> (By the way, _no_ this isn't for homework *grin*)

In the case of n == 0, there is a single combination, ().

The combinations of length n (n > 0) are just the combinations of length
n-1, with to each added the numbers 1 to n (either at the beginning or the
end).

so something like (no error checking done on the input, not tested):

def combinations(length, n):
   if length == 0:
      return [()]    # Single combination, the empty one
   
   return [ (i,)+combination for combination in combinations(length-1, n)
                             for i in range(1, n+1) ]

Excuses for the overly functional style - though it's quite neat in
this case :-).

Hmm. I just thought of ways to write that as a lambda. And I've never even
written Lisp, and no Haskell in years. Time to go write Python again :)

(Hi all, was disinterested for a while because of being busy etc, think
I'll be back now)

-- 
Remco Gerlich