0

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
aman
  • 307
  • 21
  • 48
  • 1
    Does this answer your question? [All combinations of a list of lists](https://stackoverflow.com/questions/798854/all-combinations-of-a-list-of-lists) – Tomerikoo Oct 22 '20 at 09:40
  • Oh, I should have specified it before ... But I'm looking for more of a manual iteration. – aman Oct 22 '20 at 22:31

2 Answers2

3

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)]
Arvind Kumar
  • 451
  • 2
  • 10
1

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]
HichamDz38
  • 94
  • 7
  • Can it be possibly designed into a bottom-up solution, without doing function calls (recursion) and using only recursive techniques? – aman Oct 22 '20 at 23:41
  • well you said, without recursion, but with recursive, it's the same thing, I think you mean with loops (iterations), if you have a fixed amount of group, yes, but with a dynamic amount of group, this is why we have to use recursion --> for making a dynamic number of loops depond on the data – HichamDz38 Oct 22 '20 at 23:52
  • Yeah, thanks for the recursion solution. But I want to build an optimal DP solution, and I assumed that I will be able to develop a recursive (iterations) method from this recursion method. So we might not be able to build an iteration method using loops only? – aman Oct 23 '20 at 00:14