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)
[[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
You can use some recursion based on the original element. For efficiency, add memoization , which can be done in Python quite easily (see esp.
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)
is the original route element. That is, each route element taken from
must be at least larger
Then there are two points:
It's not that hard to write it
recursively. Because for whatever element in
that you are using (which is easy to find - just check if it is less
), you just need to call
replaced with which you just used. You need to return the sum of the returned values.
Once you have it
, it's easy to wrap it in some toplevel
empty, the answer is 0).
b. If it is not, select the smallest element in
, subtract 1 from it, and call the result of the subtraction
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) - 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: 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)
source to share