Logic problems

Hey,

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

Code:

4
9   6   10
11   10
4

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.

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?

Code:

1 -> 2 -> 3 -> 4 -> 1
1 -> 3 -> 4 -> 2 -> 1
1 -> 4 -> 2 -> 3 -> 1
1 -> 2 -> 4 -> 3 ->1
etc
etc

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.

This is done by Dijkstra's algorithm IIRC. It uses a stack to find the shortest route. Look it up.

The actual implementation of the graph can be done in a number of ways. The simplest is to use a multimap, but there are other alternatives.

I've been reading through articles I have found on Google, but the code is not making much sense to me. Does anyone know of any good tutorials that talk about Dijkstra's algorithm in terms of C++ lists and sets, not graphs?

You need to figure out how to implement a graph using lists and sets.

It's very easy with a multimap, since a graph is just a mapping of vertexes to edges, and edges are just a value and destination pair.

If you can't use a multimap, you can implement one youself.

I asked about this also in another forum and here is what one person had to say:

Actually, Dijkstra's algorithm gives you the shortest paths between a given node and all the other nodes. It doesn't give you any path that visits all the nodes. What you are asking for is a solution of the traveling salesman problem, which is an infamous NP-complete problem. Nobody knows whether an efficient algorithm exists. If there are only 4 locations, you can just check all 6 orderings of locations 2, 3, and 4, but that's not going to work if you have many locations. (With 10 locations, there are already more than 360,000 orderings, and after that, each new location increases the number of orderings by at least a factor of 10.)

You should ask yourself why you need the absolute shortest path. If you can settle for one that's not quite optimal, there may be algorithms that find short paths without guaranteeing that they find the shortest one. If I remember correctly, this is true at least when the locations are points on a plane and the distance is just normal distance, but beyond that, I don't know.

In any case, this is a graph problem, so all relevant examples and code you're likely to encounter will use the language of graphs.

What about something along these lines?

Code:

// int n = number of places the user has entered
possibleCombinations = factorial(n);

for(int i = 0; i < possibleCombinations; i++)
{
  for(int x = 0; x < n; x++)
  {
    // some code here
  }
}

So if there were 5 places, 5! is 160 so the first loop would execute 160 times for 160 total possible combinations, and the inside loop would execute 5 times for each time the out loop executed, since each combination has 5 places. Now my problem still is how do I put together all of these combinations?

I found an article through Google talking about the traveling salesman problem, and it mentioned using std::next_permutation() This seems to be exactly what I need?

Originally Posted by Beowolf

I found an article through Google talking about the traveling salesman problem, and it mentioned using std::next_permutation() This seems to be exactly what I need?

Sure. For each permutation, you have to check if it is a valid path.

std::next_permutation() will keep permuting forever. When it eventually comes back to the order you started with, you know you're done.

It will actually return false when it realizes it has come back to the order you started with, you just have to keep checking the return value.

Yeah, the other forum poster was right, I did not read your post carefully enough.

next_permutation will work if you disallow revisiting each destination. Sometimes though, the least path may involve doubling back.

For my assignment I have to calculate the best route using a recursive method. I've been playing around with next_permutation() and do not see how I could implement it into a recursive method - is it even possible? Is there anywhere I can see the actual code that next_permutation calls?

Update: I found this recursive method for permutations, which seems to do what I need, but I don't understand the code:

Code:

// recvperm.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"


#include <string>
#include <iostream>

using namespace std;


void string_permutation( std::string& orig, std::string& perm )
{
	if( orig.empty() )
	{
		std::cout<<perm<<std::endl;
		return;
	}

	for(int i=0;i<orig.size();++i)
	{
		std::string orig2 = orig;

		orig2.erase(i,1);

		std::string perm2 = perm;
		
		perm2 += orig.at(i);

		string_permutation(orig2,perm2);

	} 
}

int main()
{
  
	std::string orig="ABCDE";
	std::string perm;  

	string_permutation(orig,perm);

	cout<<"Complete!"<<endl;

	system("pause");

	return 0;
}

How does this look to you? And what is "stdafx.h"?

As far as I know, "stdafx.h" is a header file automatically generated when you use Visual C++. And as far as I can see from the code, you can just get rid of that line if you want to.

Thanks, that fixed it.

I've been working to convert that method from using strings to lists and sets. Originally I had a ton of errors, but now I've managed to fix a few of them. However, I seem to be stuck now. Here is my code:

Code:

#include <string>
#include <iostream>
#include <set>
#include <list>

using namespace std;


void string_permutation(set<int>& orig, list<int>& perm )
{ // line 10
	if( orig.empty() )
	{
		list<int>::iterator theIterator;
        for(theIterator = perm.begin(); theIterator != perm.end(); theIterator++)
        {
            cout << *theIterator << "\n";
        }
		return;
	}

	for(int i = 0; i < orig.size(); i++) // line 21
	{
		list<int> orig2 = orig;

		orig2.erase(i,1); // line 25

		list<int> perm2 = perm;
		
		perm2.push_front(orig.find(i)); // line 29

		string_permutation(orig2,perm2); // line 31

	} 
}

int main()
{
  
	int myInts[] = {1, 3, 2, 4};
    set<int> orig(myInts, myInts+4);
	list<int> perm;  

	string_permutation(orig, perm);

	system("Pause");

	return 0;
}

And the compiler errors:

Code:

21 permutation.cpp [Warning] comparison between signed and unsigned integer expressions 
23 permutation.cpp conversion from `std::set<int, std::less<int>, std::allocator<int> >' to non-scalar type `std::list<int, std::allocator<int> >' requested 
25 permutation.cpp invalid conversion from `int' to `std::_List_node_base*' 
25 permutation.cpp   initializing argument 1 of `std::_List_iterator<_Tp>::_List_iterator(std::_List_node_base*) [with _Tp = int]' 
25 permutation.cpp invalid conversion from `int' to `std::_List_node_base*' 
25 permutation.cpp   initializing argument 1 of `std::_List_iterator<_Tp>::_List_iterator(std::_List_node_base*) [with _Tp = int]' 
29 permutation.cpp no matching function for call to `std::list<int, std::allocator<int> >::push_front(std::_Rb_tree_const_iterator<int>)' 
 note C:\Applications\Dev-Cpp\include\c++\3.4.2\bits\stl_list.h:753 candidates are: void std::list<_Tp, _Alloc>::push_front(const _Tp&) [with _Tp = int, _Alloc = std::allocator<int>] 
31 permutation.cpp invalid initialization of reference of type 'std::set<int, std::less<int>, std::allocator<int> >&' from expression of type 'std::list<int, std::allocator<int> >' 
10 permutation.cpp in passing argument 1 of `void string_permutation(std::set<int, std::less<int>, std::allocator<int> >&, std::list<int, std::allocator<int> >&)'

First, fix line 23. You're trying to dump a set into a list. Furthermore, you're trying to pass that on as an argument to a function which isn't defined for that argument.
Last, you're lists aren't defined to have pointers/iterators as elements.

I fixed line 23.

Last, you're lists aren't defined to have pointers/iterators as elements.

Sorry, what does this mean? The only place I use pointers/iterators is at line 13 and 14 (the for loop inside of if orig.empty()) and that compilers fine.