Recursive function, how?

This is the place for queries that don't fit in any of the other categories.

Recursive function, how?

Postby pnemeth » Tue Mar 12, 2013 11:10 am

Dear all,

I know it is not wise to work with recursive functions, but I think I need one. I have two vectors (arrays: state1, state2) and would like to interpolate in between with a certain step size (array: step). For three dimensions this function works:

Code: Select all
def recurse(state1, state2, step):
  var1 =  state1[0]
  while var1 <=  state2[0]:
    var2 =  state1[1]
    while var2 <=  state2[1]:
      var3 = state1[2]
      while var3 <=  state2[2]:
        print var1,var2,var3
        var3 *= step[2]
      var2 += step[1]   
    var1 += step[0]


However, I will need to use vectors up to dimension 30. Moreover, the first two dimensions are additive and the rest are multiplicative.
How could I generalize these nested loops to a flexible recursive function?

Thanks in advance,
Peter
pnemeth
 
Posts: 3
Joined: Tue Mar 12, 2013 10:29 am

Re: Recursive function, how?

Postby setrofim » Tue Mar 12, 2013 4:17 pm

pnemeth wrote:I know it is not wise to work with recursive functions

Not always. You have to be careful when dealing with recursion, but sometime recursion provides the most elegant solution.
pnemeth wrote:but I think I need one

Nope, in this case, recursion isn't necessary:
Code: Select all
from operator import add, mul

example_state1 = [1,2,3]
example_state2 = [10,30,24]
example_steps = [3,5,2]
example_ops = [add,add,mul]


def interpolate(state1, state2, steps, ops):
    results = []
    for v1, v2, s, o in zip(state1, state2, steps, ops):
        r = []
        v = v1
        while v <= v2:
            r.append(v)
            v = o(v,s)
        results.append(r)
    return results


if __name__=='__main__':
    results = interpolate(example_state1, example_state2, example_steps, example_ops)

    from pprint import pprint
    pprint(results)

Note that this function makes two assumptions about its inputs: that all input lists are of the same length, and that the values in state2 are always greater or equal to the values in state1 for a positive step, and that this solution will not work for negative steps, as that will result in oscillation between positive and negative values in case of multiplication, which would break the while check. Also note that if you were dealing with additive interpolation only, a better way to implement that would be with Python's built-in range() function, i.e. results.append(range(v1, v2, s)) instead of the while loop.
setrofim
 
Posts: 288
Joined: Mon Mar 04, 2013 7:52 pm

Re: Recursive function, how?

Postby pnemeth » Wed Mar 13, 2013 12:15 pm

Hi Setrofim,


Thanks for your reply and for looking into my problem! I forgot about "zip", it is really handy here. Now I am closer to a solution. However, using your example, your code returns this list:

Code: Select all
[[1, 4, 7, 10], [2, 7, 12, 17, 22, 27], [3, 6, 12, 24]]


Instead, I would need:

Code: Select all
1 2 3
1 2 6
1 2 12
1 2 24
1 7 3
1 7 6
1 7 12
1 7 24
1 12 3
1 12 6
1 12 12
1 12 24
1 17 3
1 17 6
1 17 12
1 17 24
1 22 3
1 22 6
1 22 12
1 22 24
1 27 3
1 27 6
1 27 12
1 27 24
4 2 3
4 2 6
4 2 12
4 2 24
4 7 3
4 7 6
4 7 12
4 7 24
4 12 3
4 12 6
4 12 12
4 12 24
4 17 3
4 17 6
4 17 12
4 17 24
4 22 3
4 22 6
4 22 12
4 22 24
4 27 3
4 27 6
4 27 12
4 27 24
7 2 3
7 2 6
7 2 12
7 2 24
7 7 3
7 7 6
7 7 12
7 7 24
7 12 3
7 12 6
7 12 12
7 12 24
7 17 3
7 17 6
7 17 12
7 17 24
7 22 3
7 22 6
7 22 12
7 22 24
7 27 3
7 27 6
7 27 12
7 27 24
10 2 3
10 2 6
10 2 12
10 2 24
10 7 3
10 7 6
10 7 12
10 7 24
10 12 3
10 12 6
10 12 12
10 12 24
10 17 3
10 17 6
10 17 12
10 17 24
10 22 3
10 22 6
10 22 12
10 22 24
10 27 3
10 27 6
10 27 12
10 27 24


So I still need to loop through all the dimensions. This is why I tried with recursion in the first place. What do you think?

cheers,
Peter
pnemeth
 
Posts: 3
Joined: Tue Mar 12, 2013 10:29 am

Re: Recursive function, how?

Postby setrofim » Wed Mar 13, 2013 12:30 pm

itertools.product does exactly what you need:
Code: Select all
from operator import add, mul
from itertools import product

example_state1 = [1,2,3]
example_state2 = [10,30,24]
example_steps = [3,5,2]
example_ops = [add,add,mul]


def interpolate(state1, state2, steps, ops):
    results = []
    for v1, v2, s, o in zip(state1, state2, steps, ops):
        r = []
        v = v1
        while v <= v2:
            r.append(v)
            v = o(v,s)
        results.append(r)
    return product(*results)


if __name__=='__main__':
    results = interpolate(example_state1, example_state2, example_steps, example_ops)

    for  r in results:
        print ' '.join(map(str,r))

setrofim
 
Posts: 288
Joined: Mon Mar 04, 2013 7:52 pm

Re: Recursive function, how?

Postby pnemeth » Wed Mar 13, 2013 1:25 pm

Yes, yes, this is it and not least, it is fast.
Thank you!
pnemeth
 
Posts: 3
Joined: Tue Mar 12, 2013 10:29 am


Return to General Coding Help

Who is online

Users browsing this forum: Bing [Bot], Majestic-12 [Bot] and 2 guests