Michael - 7 months ago 35

Python Question

My goal for the program is the following:

Given *any shape* (represented as enumerated points and their connections to other points), return a *list* containg *all possible paths* (as strings/lists/...). A path is a 'drawing' of the given shape, in which:

The following code is essentially what I've come up with so far. It's not the code of the actual program, but the basic semantics are the same (i.e. if this code will work, my program will work too).

`"""`

Example used:

2

/ \

/ \

/ \

1-------3

"""

from copy import deepcopy

points = {1: [2,3],

2: [1,3],

3: [1,2]}

def find_paths(prev_point, points):

for current_point in points[prev_point]:

points[current_point].remove(prev_point)

points[prev_point].remove(current_point)

return [prev_point] + find_paths(current_point, points)

return [prev_point]

def collect(points):

results = []

for first_point in points:

result = find_paths(first_point, deepcopy(points))

results.append(result)

return results

print(collect(points))

`for`

`f`

`return`

`f`

EDIT: The generator-version I had simply replaced the

`return`

`find_paths `

`yield `

So the last two lines look like:

...

yield [prev_point] + find_paths(current_point, points)

yield [prev_point]

Additionally, I played around with a 'flattener' for generators, but it didn't work at all:

def flatten(x):

if callable(x):

for i in x:

yield flatten(i)

yield x

def func():

yield 1

lis = [1,2,func]

for f in flatten(lis):

print(f)

Answer

I think the following works. I based it off of your original code, but did a few things (some necessary, some not):

- Rename parameters in
`find_paths`

to make more sense for me. We are working with the`current_point`

not the`previous_point`

, etc. - Add an end condition to stop recursion.
- Make a copy of points for every possible path being generated and return (yield) each one of those possible paths. Your original code didn't have logic for this since it only expected one result per call to
`find_paths`

, but that doesn't really make sense when using recursion like this. I also`extend`

my final result for the same reason.

Here is the code:

```
from copy import deepcopy
points = {1: [2,3],
2: [1,3],
3: [1,2]}
def find_paths(current_point, points):
if len(points[current_point]) == 0:
# End condition: have we found a complete path? Then yield
if all(not v for v in points.values()):
yield [current_point]
else:
for next_point in points[current_point]:
new_points = deepcopy(points)
new_points[current_point].remove(next_point)
new_points[next_point].remove(current_point)
paths = find_paths(next_point, new_points)
for path in paths:
yield [current_point] + path
def collect(points):
results = []
for first_point in points:
result = find_paths(first_point, deepcopy(points))
results.extend(list(result))
return results
print(collect(points))
```

Results in:

```
[1, 2, 3, 1]
[1, 3, 2, 1]
[2, 1, 3, 2]
[2, 3, 1, 2]
[3, 1, 2, 3]
[3, 2, 1, 3]
```

Your original example image should work with the following:

```
points = {
1: [2,3],
2: [1,3,4,5],
3: [1,2,4,5],
4: [2,3,5],
5: [2,3,4],
}
```

Source (Stackoverflow)