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)

Admin 1
Viewed 244

I have a list of lists of ordered pairs [[(1,2), (3,3), (7,5)],[(2,3), (3,2), (6,4), (2,4)]] (not necessarily 2 sublists). Each ordered pair corresponds to a valid path (eg. from node 1 to node 2 for (1,2)) and each sublist corresponds to a level. I would like to find the number of paths through a list such that I am always following an ordered pair path.

For the example above, (1,2), (2,3), (1,2), (2,4), and (3,3), (3,2) are all the valid paths. Thus, the program would output 3.

I was thinking about hashing on the 2nd value for each list, with the key being the number of left pairs ({2: 1, 3: 1, 5:1}), but this seems rather inefficient as I have to then somehow multiply based on the number of times the key of the previous list iteration appears in the value of the current list iteration.

It seems similar to a graph traversal problem, but DFS would require large space complexity (the function to calculate the ordered pairs returns a sublist at a time rather than the full list).

python-2.7 graph-algorithm list algorithm python
1 Answers

[Note: As, you didn't clearly speak about what output you want, I am assuming you want the total no of possible paths from given sublists].

Interestingly, this problem does not require graph knowledge to solve. You can solve this problem using normal algorithmic knowledge(the approach I'm taking to solve the problem is called dynamic programming).

At first let me break the approach:

  1. for simplicity let's use a simple example:
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.
  1. Now, how can we simply express, 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"

I hope, the concept above is clear to you now. If not read again, cause we'll use it to solve the problem.

Now, we just have to find out the starting state. For the first level, the way of entering 1 and 4 is one, but enetring 2 or 3 is zero. I hope this is also clear to you.

Now, let's just write the solution:


# 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 hope the solution is clear, cause, it's just the reflection of what I said earlier.

The I/O:

for given input:

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

the output is:

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

The complexity of this solution is O(n * k), where n is number of nodes and k is number of sublists.

user_88643370
Related