# 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]
```

```
+3

source to share

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`

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)
```

```
+4

source

All Articles