I am trying to design a recursive method to figure out a certain problem. I know what I have to do but I am not really sure how to go around implementing it. Here it is:
The user inputs n locations, say 4, and the distance between each location. For example
The first line is the number of locations there are, in this case 4. The next three lines are the distance between locations. Line 2 corresponds to the distance of location 1 to loc. 2, 3, and 4 - so between 1 and 2 there is a distance of 9, between 1 and 3 there is a distance of 6, and between 1 and 4 there is a distance of 10. Line 3 corresponds to the distance between 2 - 3 and 2 - 4, and line 4 is the distance between 3 - 4.Code:4 9 6 10 11 10 4
Now my goal is to find the shortest possible route between all four locations, starting with location 1 and ending back at location 1, hitting all of the locations inbetween. For example, it may look like "1 3 2 4 1" which would mean start at loc 1, travel to loc 3, from 3 travel to 2, from 2 travel to 4, and from 4 back to one.
Here is what I know I must do: find the sum of every combination and then compare the sums to see which one is the smallest. My problem is that I am not sure how to code this - how do I put together every possible combination?
I am using lists and sets if that is of any help. I think I know how to do this if I was able to use two dimensional arrays and n was a constant, but I can't quite figure it out recursively using sets and lists.Code:1 -> 2 -> 3 -> 4 -> 1 1 -> 3 -> 4 -> 2 -> 1 1 -> 4 -> 2 -> 3 -> 1 1 -> 2 -> 4 -> 3 ->1 etc etc