# Logic problems

Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last
• 10-25-2007
Beowolf
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.
• 10-25-2007
King Mir
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.
• 10-25-2007
Beowolf
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?
• 10-26-2007
King Mir
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.
• 10-28-2007
Beowolf
I asked about this also in another forum and here is what one person had to say:

Quote:

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?
• 10-29-2007
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?
• 10-29-2007
brewbuck
Quote:

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.
• 10-29-2007
Daved
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.
• 10-29-2007
King Mir
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.
• 10-29-2007
Beowolf
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?
• 10-29-2007
Beowolf
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"?
• 10-29-2007
cunnus88
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.
• 10-29-2007
Beowolf
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> >&)'```
• 10-29-2007
cunnus88
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.
• 10-29-2007
Beowolf
I fixed line 23.

Quote:

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.
Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last