2

Eventually, I would like to generalize this solutions to work with a Tuple of any length. I think recursion is required for that, but I haven't been able to do it.

def combineRanges(maxValues) :
    for x in range(0, maxValues[0]) :
        for y in range(0, maxValues[1]) :
            for z in range(0, maxValues[2]) :
                print (str(x) + '-' + str(y) + '-' + str(z));

m = (6,9,20);    
combineRanges(m);

http://repl.it/WiZ

6

There is no need for recursion here; you can use itertools.product, map and tuple unpacking:

from itertools import product

def combine_ranges(max_values):
    for t in product(*map(range, max_values)):
        print("-".join(map(str, t)))

A shorter example:

>>> combine_ranges((2, 2, 2, 2))
0-0-0-0
0-0-0-1
0-0-1-0
0-0-1-1
0-1-0-0
0-1-0-1
0-1-1-0
0-1-1-1
1-0-0-0
1-0-0-1
1-0-1-0
1-0-1-1
1-1-0-0
1-1-0-1
1-1-1-0
1-1-1-1

Note use of PEP-8-compliant names.

  • 2
    The recursion limit is not a concern here. Even for very short max_values the number of combinations quickly grows beyond reason. [2] * 100 is probably already too large to be enumerated on a physical machine (2^100) and it only needs 100 levels of recursion. More realistic is at most a dozen recursive calls. – user7043 Aug 12 '14 at 16:38
  • @delnan fair point, I will edit that out – jonrsharpe Aug 12 '14 at 16:39
  • Good to know. I am learning when to use recursion and when to use looping. – Shaun Luttin Aug 12 '14 at 17:26
1

Recursion is not required, but it's one of the clearest ways to do unknown levels of nested loops. You will only use one level of stack per element in your input tuple, so you have a fair bit of breathing room.

For a recursive function you need a base case and a recursive case. The base case is when you have zero elements in your tuple, which is where you print your result. The recursive case is where you do each nested loop and append the results to the level below.

def combineRanges(maxValues, result=()):
  if len(maxValues) is 0:
    print("-".join(result))
    return

  for x in range(0, maxValues[0]):
    combineRanges(maxValues[1:], result + (str(x),))

Each recursive call pulls one element off the front of maxValues and adds one result to the result tuple, until maxValues is empty. This type of recursion is a little trickier because you are accumulating the result in an argument, but this pattern is very useful and comes up a lot, so it is worth learning. Also, python's lists aren't immutable, which is why I use a tuple to hold the result.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.