[Tutor] Recursive combinations?

Remco Gerlich scarblac@pino.selwerd.nl
Wed, 15 Aug 2001 14:18:00 +0200

On  0, Andrew Wilkins <toodles@yifan.net> wrote:
> Thanks Remco!
> I tried it out - doesn't do _quite_ what I wanted, but with that (beautiful)
> code I can change it to do what I want! It just needs to remove reverse
> orders (eg. (1,2) and (2,1), and remove like elements in pairs (eg. (1,1)).

Oh, right. I'm immediately back to my old style of posting - almost, but not
quite :)

Both are easily remedied by generating only combinations that are in
strictly ascending (or descending) order.

That means using range(1, combination[0]), but unfortunately that needs
an extra check for length == 1.

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

Remco Gerlich