CODEWITHSUNDEEP
python
aman
aman

Reputation: 401

Iterate through 2D array like a graph

I have stored a graph in a 2D array and I want to print all the possible path from any directed graph going from left to right through groups. I have given an example below and want to print all the paths from the first group (in this example G1) to any last group (in this example G3). I'm not able to build a recursive or recursion method to print all the paths with any amount of groups. So I need help with building a manual iteration system/algorithm. Thanks.

graph:

enter image description here

script.py

map = [
  [1,2],
  [3,4,5],
  [6,7]
]

// Print all paths
// Note :- every array in the map is a group

output:

1 -> 3 -> 6
1 -> 3 -> 7
1 -> 4 -> 6
1 -> 4 -> 7
1 -> 5 -> 6
1 -> 5 -> 7
2 -> 3 -> 6
2 -> 3 -> 7
2 -> 4 -> 6
2 -> 4 -> 7
2 -> 5 -> 6
2 -> 5 -> 7

Upvotes: 0

Views: 242

Answers (2)

HichamDz38
HichamDz38

Reputation: 104

this is a solution using recursion, and without using libraries it will work with any amount of groups

mp = [
  [1,2],
  [3,4,5],
  [6,7]
]

def possible_path(M,index,combination):
    for i in M[index]:  
        if index<len(M)-1:
            possible_path(M,index+1,combination+[i])
        else:
            print(combination+[i])

possible_path(mp,0,[])

this is the output:

[1, 3, 6]
[1, 3, 7]
[1, 4, 6]
[1, 4, 7]
[1, 5, 6]
[1, 5, 7]
[2, 3, 6]
[2, 3, 7]
[2, 4, 6]
[2, 4, 7]
[2, 5, 6]
[2, 5, 7]

Upvotes: 1

Arvind Kumar
Arvind Kumar

Reputation: 451

As per the description, you need the possible combinations of all the paths you have mentioned in the variable 'map'. So you can use itertools to get all the possible combinations of the paths.

I guess this should work for you:

import itertools
pattern = list(itertools.product(*map))
print(pattern)

Output

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

Upvotes: 3

Related Questions