Number of routes in the list of lists

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

and.

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)