How to get data from nested lists recursively?-CodePudding

I have a nested array of arbitrary length and trying to retrieve data from it in the following order: items in the [0] element of the array form somewhat like a tree and as a result I should return all possible combinations with them.

For example:

some_list = [[1, 2], [3, 4], [5, 6, 7]]

the result should be:

[1, 3, 5], [1, 3, 6], [1, 3, 7], [1, 4, 5], [1, 4, 6], [1, 4, 7], 
[2, 3, 5], [2, 3, 6], [2, 3, 7], [2, 4, 5], [2, 4, 6], [2, 4, 7]

I tried loops but they do not seem a good decision. I think it should be recursion, but don't know how to apply it.

CodePudding user response：

You can do it with nested for loops, or for convenience, with itertools.product:

from itertools import product

some_list = [[1, 2], [3, 4], [5, 6, 7]]

prod = [list(i) for i in product(*some_list)]
print(prod)

Output:

[[1, 3, 5], [1, 3, 6], [1, 3, 7], [1, 4, 5], [1, 4, 6], [1, 4, 7], [2, 3, 5], [2, 3, 6], [2, 3, 7], [2, 4, 5], [2, 4, 6], [2, 4, 7]]

CodePudding user response：

this is an example of a recursive function that would calculate the cartesian product of all the input lists

def cp(x):
    l = []

    # loop over the lists in the list
    # if there is only 1 list left in the input then return it 

    if len(x) > 1:
        for i in x[0]:   # loop over the first list in the input
            for j in cp(x[1:]):   #  loop over the cartesian product of the remaining lists in the input
                l.append([i])     #  add a new sub-list starting with value of i 
                if isinstance(j,list):  # extend it with the result of the cartesian product of the remaining lists
                    l[-1].extend(j)
                else:
                    l[-1].append(j)
    else:
        l = x[0]

    return l


print(cp([[1, 2], [3, 4], [5, 6, 7]]))

gives the output

[[1, 3, 5], [1, 3, 6], [1, 3, 7], [1, 4, 5], [1, 4, 6], [1, 4, 7], [2, 3, 5], [2, 3, 6], [2, 3, 7], [2, 4, 5], [2, 4, 6], [2, 4, 7]]

have a look here for implementations in different programming languages: https://rosettacode.org/wiki/Cartesian_product_of_two_or_more_lists