给定有序对（跳跃）的子列表列表，我如何计算通过列表的路径数（每条路径都是一系列跳跃）

Question

我有一个有序对列表列表 [[(1,2), (3,3), (7,5)],[(2,3), (3,2), (6,4), (2,4)]]（不一定是 2 个子列表）。每个有序对对应一个有效路径（例如，对于 (1,2)，从节点 1 到节点 2），每个子列表对应一个级别。我想找到列表中的路径数，以便我始终遵循有序的路径对。

对于上面的示例，(1,2), (2,3)、(1,2), (2,4)和(3,3), (3,2)都是有效路径。因此，程序将输出 3.

我正在考虑对每个列表的第二个值进行哈希处理，关键是左对的数量（{2: 1, 3: 1, 5:1}），但这似乎效率很低，因为我必须以某种方式乘以前一个列表迭代的键出现在当前列表迭代的值中的次数。

这似乎类似于图形遍历问题，但 DFS 需要很大的 space 复杂度（计算有序对的函数 returns 一次计算一个子列表而不是完整列表）。

Answer 1

[注意：因为，你没有明确说明你想要什么输出，我假设你想要给定子列表中可能路径的总数]。

有趣的是，这个问题不需要图知识来解决。你可以使用正常的算法知识解决这个问题（我用来解决这个问题的方法称为动态规划）。

首先让我破解方法：

为简单起见，让我们使用一个简单的示例：

let, input = [[(1, 2), (4, 2)], [(2, 3)]]

Now, let's think about, how many ways are there to reach node 3. Well,
there are (1, 2, 3) and (4, 2, 3), so two ways to reach 3.

现在，我们如何简单地表达，the number of ways to reach 3。

Note: reaching 3, requires the knowledge of reaching 2.
So, we'll try to express the number of reaching 3 in terms of reaching 2.
And, knowledge of number of reaching 2 can be obtained from previous
level's information. We can say like below:

If there is a pair (u, v), then, pres_ways[v] += prev_ways[u].
Here, "pres_ways[x]" denotes, present level's ways of reaching "any node x"
and   "prev_ways[x]" denotes, previous level's ways of reaching "any node x"

希望您现在已经清楚上面的概念了。如果没有再读，因为我们会用它来解决问题。

现在，我们只需要找出起始状态。第一级，1和4的输入方式是one，而2或3的输入方式是zero。我希望你也清楚这一点。

现在，让我们写下解决方案：


# note: "ll" denotes lists of lists i.e. the input
# save your input in "ll"

# ll = [[(x, y)], [(u, v)]]

# let's assume, nodes are numbered from 1 to n

n = 7 # change the number as necessary or take input from file, as you wish

# initial state
prev = [0] * (n+1)
for u, v in ll[0]:
    prev[u] = 1

for l in ll:
    pres = [0] * (n+1)
    for u, v in l:
        pres[v] += prev[u]
    prev = pres

tot = 0
for i in range(1, n+1):
    tot += prev[i]
    print("The number of ways to reach {} is {}".format(i, prev[i]))

print("total: {}".format(tot))

我希望解决方案是明确的，因为，这只是我之前所说内容的反映。

I/O:

对于给定的输入：

ll = [
    [(1, 2), (3, 3), (7, 5)],
    [(2, 3), (3, 2), (6, 4), (2, 4)]
]

输出是：

The number of ways to reach 1 is 0
The number of ways to reach 2 is 1
The number of ways to reach 3 is 1
The number of ways to reach 4 is 1
The number of ways to reach 5 is 0
The number of ways to reach 6 is 0
The number of ways to reach 7 is 0
total: 3

此解决方案的复杂度为 O(n * k)，其中 n 是节点数，k 是子列表数。

给定有序对（跳跃）的子列表列表，我如何计算通过列表的路径数（每条路径都是一系列跳跃）

Given a list of sublists of ordered pairs (hops), how can I count the number of paths through list (each path is a sequence of hops)

python

algorithm

list

graph-algorithm

python-2.7