python - 列表列表中的路由数

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 在下面的评论中指出的 functools.lru_cache)。

假设你有这样一个函数:

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 中 - 只需:

一个。如果 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)