列表列表中的路由数

Question

有没有一种方法可以计算列表中的路由数？规则是在每个子列表中选取一个元素以形成一个列表，新列表中的值是升序的。（列表或子列表的长度不是固定的）

环境质量。 列表是

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

满足要求的方法有三种：

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

Answer 1

可以使用基于起始元素的某种递归。为了提高效率，添加memoization，即can be done in Python quite easily（请参见@abarnert在下面的注释中指出的^{}）。你知道吗

假设你有这样一个函数：

def num_routes_starting_with(list_of_lists, starting_elem)

其中starting_elem是路由的起始元素。也就是说，从list_of_lists[0]获取的路由中的每个元素必须至少大于starting_elem。你知道吗

还有两点：

1. 递归地编写num_routes_starting_with代码并不难。因为对于list_of_lists[0]中您使用的任何元素（这很容易找到-只要检查它是否小于starting_elem），您只需要调用routes_starting_with，用list_of_lists[1: ]替换starting_elem。您需要返回返回值的总和。

2. 一旦你有了num_routes_starting_with，就可以很容易地把它包装成顶级的routes——简单地说：

a.如果list_of_lists为空，则答案为0）。你知道吗

如果不是，则选择list_of_lists[0]中最小的元素，从中减去1，并用list_of_lists和减法结果调用numroutes_starting_with。你知道吗

---

下面是它的整体外观：

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)