# [Tutor] Recursive combinations?

**Remco Gerlich
**
scarblac@pino.selwerd.nl

*Wed, 15 Aug 2001 12:26:29 +0200*

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