Adding logic to recursive function

Question

The below function produces a cartesian product of the input lists.

How can you make it only yield results where the last two numbers are even?

I'm just trying to see an example of how to correctly add logic to a function of this type.

def product(ar_list):
    if not ar_list:
        yield ()
    else:
        for a in ar_list[0]:
            for prod in product(ar_list[1:]):
                out= (a,)+prod
                yield out

ar_list=[[1,2],[3,4],[5,6,7]]              
                
print(list(product(ar_list)))

In this case you need to read the future a little. Test if ar_list has two elements or less, and if so, only yield elements where prod is even. (i.e. yield if ar_list is longer than two elements, or prod is even.) This is not possible if ar_list is an iterator, as "reading the future" will exhaust it; in this case, you will either need to cheat by duping the iterable before counting the remaining elements, or — simpler — just filter (non-recursively) the results of this generator. — Amadan
– Amadan, Commented Apr 16, 2021 at 3:00
To be clear: is the expected output: [(1, 4, 6), (2, 4, 6)]? If not, please update your post with the expected output. — Michael Ruth
– Michael Ruth, Commented Apr 16, 2021 at 3:58

Michael Ruth · Accepted Answer · 2021-04-16 04:48:48Z

1

You'll need to establish an additional recursive case for len(ar_list) == 2. As stated previously in the comments, this works only when ar_list.__len__ is defined.

def product(ar_list):
    if not ar_list:
        yield ()
    elif len(ar_list) == 2:
        ar_list[0] = [x for x in ar_list[0] if x % 2 == 0]
        ar_list[1] = [x for x in ar_list[1] if x % 2 == 0]
        for a in ar_list[0]:
            for prod in product(ar_list[1:]):
                out = (a,) + prod
                yield out            
    else:
        for a in ar_list[0]:
            for prod in product(ar_list[1:]):
                out= (a,) + prod
                yield out

Really, the simplest way is to filter the results of itertools.product and this solution works when ar_list.__len__ is not defined.

import itertools


def product(ar_list):
    for prod in itertools.product(*ar_list):
        if prod[-2] % 2 == 0 and prod[-1] % 2 == 0:
            yield prod

A potentially more efficient solution is to filter prior to generating the Cartesian product but does require ar_list to be subscriptable.

import itertools


def product(ar_list):
    ar_list[-2] = [x for x in ar_list[-2] if x % 2 == 0]
    ar_list[-1] = [x for x in ar_list[-1] if x % 2 == 0]
    for prod in itertools.product(*ar_list):
        if prod[-2] % 2 == 0 and prod[-1] % 2 == 0:
            yield prod

answered Apr 16, 2021 at 4:48

Michael Ruth

3,5441 gold badge26 silver badges34 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

blhsing Over a year ago

The recursive solution does not work when the length of the input list is 1. The other two solutions using itertools.product do not answer the question since the question specifically asks about adding logic to an existing recursive function.

Michael Ruth Over a year ago

@blhsing, I'd argue that "How can you make it only yield results where the last two numbers are even?" implies that ar_list has at least two elements. This should be clarified by the asker. You are certainly correct on your last two criticisms.

blhsing Over a year ago

If the case where the length of the input list is 1 is not to be dealt with then you (and the OP) should not go even further to deal with the case where the length of the input list is 0 to begin with, as you do with the statement if not ar_list:. Having that statement implies that it is the base case of the recursion, and that all subsequent cases onwards should be handled properly.

blhsing · Accepted Answer · 2021-04-16 04:45:53Z

1

You can add a conditional statement that checks if the length of the current input list is still greater than 2, or if not, check if the current item is even, and only yield output for the current item if one of the two conditions is true:

def product(ar_list):
    if not ar_list:
        yield ()
    else:
        for a in ar_list[0]:
            if len(ar_list) > 2 or a % 2 == 0: # <== add this line
                for prod in product(ar_list[1:]):
                    out = (a,) + prod
                    yield out

answered Apr 16, 2021 at 4:45

blhsing

109k9 gold badges88 silver badges132 bronze badges

Collectives™ on Stack Overflow

Adding logic to recursive function

2 Answers 2

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related