Number of routes in the list of lists

Is it possible to calculate the number of routes in a list of lists? The rule is to select an item in each sub-list to form a list, and the value in the new list increases. (The length of the list or subscriptions is not fixed)

eq list

[[1, 10], [5, 16], [3, 20]]


There are three ways to fulfill the requirement:

[1, 5, 20]
[1, 16, 20]
[10, 16, 20]



source to share

1 answer

You can use some recursion based on the original element. For efficiency, add memoization , which can be done in Python quite easily (see esp. functools.lru_cache

As pointed out by @abarnert in the comments below).

Let's say you have a function like this:

def num_routes_starting_with(list_of_lists, starting_elem)


where starting_elem

is the original route element. That is, each route element taken from list_of_lists[0]

must be at least larger starting_elem


Then there are two points:

  • It's not that hard to write it num_routes_starting_with

    recursively. Because for whatever element in list_of_lists[0]

    that you are using (which is easy to find - just check if it is less starting_elem

    ), you just need to call routes_starting_with

    with list_of_lists[1: ]

    and starting_elem

    replaced with which you just used. You need to return the sum of the returned values.

  • Once you have it num_routes_starting_with

    , it's easy to wrap it in some toplevel routes

    - just:

and. If list_of_lists

empty, the answer is 0).

b. If it is not, select the smallest element in list_of_lists[0]

, subtract 1 from it, and call the result of the subtraction numroutes_starting_with

with list_of_lists


This is how it looks in general:

def num_routes(list_of_lists):
    if len(list_of_lists) == 0:
        return 0

    return num_routes_starting_with(list_of_lists, min(list_of_lists[0]) - 1)

# You should add here some memoization decorator, something like:
# @memoized
def num_routes_starting_with(list_of_lists, starting_elem):
    if not list_of_lists:
        return 1

    s = 0
    for e in list_of_lists[0]:
        if e > starting_elem:
            s += num_routes_starting_with(list_of_lists[1: ], e)
    return s

list_of_lists = [[1, 10], [5, 16], [3, 20]]
print num_routes(list_of_lists)




All Articles