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:

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?

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?

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.

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.

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.

What does this error mean?

Code:

---

25 permutation.cpp invalid conversion from `int' to `std::_List_node_base*'

---

I know I am performing my erase method wrong. It has to take in an iterator, correct? How do I create an iterator that is pointer to the location i in the list?

Maybe something like this?

Code:

---

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

  iPtr = orig2.begin();

  orig2.erase(iPtr);

  list<int> perm2 = perm;
               
  perm2.push_front(orig.find(iPtr));

  string_permutation(orig2,perm2);
}

---

You don't, at least not efficiently. There is no random access for lists because it is such an inefficient operation; you'd have to use std::advance to do it. Instead, change your for loop to use iterators to iterate over the list instead of an index i.

Ok, so something like this?

Code:

---

set<int>::iterator theIterator;
for(theIterator = orig.begin(); theIterator != orig.end(); theIterator++)
{
    set<int> orig2 = orig;

    orig2.erase(theIterator);

    list<int> perm2 = perm;
               
    perm2.push_front(orig.find(theIterator));

    string_permutation(orig2,perm2);
}

---

Is it legal to find an element in a set and then push that element into a list?

>> orig2.erase(theIterator);
That won't work because theIterator is an iterator pointing to the orig set, so you can't use it to erase an element in the orig2 set. If you want to erase a value in the orig2 set, you just have to dereference the iterator. So maybe orig2.erase(*theIterator); would work. I haven't followed the logic of your code closely enough to know for sure.

>> perm2.push_front(orig.find(theIterator));
This won't work either. find doesn't return something that can be pushed on to a list. What are you trying to do?

What I am trying to to is to take this code below and implement it using lists instead of strings.

Code:

---

#include <string>
#include <iostream>

using namespace std;


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

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

                orig2.erase(i,1);

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

                string_permutation(orig2,perm2);

        }
}

int main()
{
 
        string orig = "1234";
        string perm; 

        string_permutation(orig,perm);

        system("pause");

        return 0;
}

---

But I am having a lot of trouble doing this and just seem to be confusing myself (and you guys) even more.

The method has two parameters - a list as the first param (taken from a global variable)(we can ignore that right now), and a set as the second param. The set has all the locations, in my test case the set would look like {1, 2, 3, 4}. I need the method to use the set to find all the possible permutations and store them in a temp list (since they won't be ordered nicely). In a different method not depicted here I find the total distance of the temp list and if it is less than the distance of the last list, the global list that was brought in as the first parameter gets updated to the new list. But like I said, we can ignore that for now.

In the code I have above the method finds all the possible permutations of the string "1234". I need it to use a list instead. I need the method to assign each permutation into a temporary list variable (which will be overwritten each time the loop executes, which is fine).

Ok, look at each piece, understand what it is doing, then update it accordingly. More specifically, understand the difference between a value and an iterator, and the difference between an iterator and an index. Understand what each function or operation returns. Understand what each function expects as a parameter. Then modify accordingly.

For example, in this line:

Code:

---

perm2 += orig.at(i);

---

• perm2 is a string. operator+= on a string expects either another string or a character value. It then appends that string or character to the end of perm2.
• orig is a string. The at() function expects an index. i is an index, so orig.at(i) is an acceptable way to call at().
• at() returns the character value at the specified index. So passing the index i to at means orig.at(i) will return a character value at the specific index i. Since you are looping through indexes from 0 to the orig string's size, then you can think of it as getting the character value at the current position in the orig string.
• Now += expects a string or a character value, and orig.at(i) returns a character value, so it works. perm2 appends the current character value in orig.

Now look at your own code and see if you can replicate the behavior. To append to a list you use push_back. You cannot append to a set. To get the current value in a list or set you should be iterating over it in the for loop, and you dereference the iterator (*theIterator). Can you put those facts together?

Thanks, that helped a lot.

I have edited my code and it now compiles, however I am stuck in an infinite loop (the "Processing\n" part repeats forever)

Code:

---

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

using namespace std;


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

    list<int>::iterator theIterator;
        for(theIterator = orig.begin(); theIterator != orig.end(); theIterator++)
        {
        cout << "Processing\n";
                list<int> orig2 = orig;

                orig2.erase(theIterator);

                list<int> perm2 = perm;
               
                perm2.push_back(*theIterator);

                string_permutation(orig2,perm2);

        }
}

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

        string_permutation(orig,perm);

        system("Pause");

        return 0;
}

---

>> orig2.erase(theIterator);
This is still the same problem I mentioned before.

In the string code you had this:

Code:

---

orig2.erase(i,1);

---

That looks in the orig2 string and erases the item that you are currently on in the iteration over the orig string.

For the list version, the current value is what theIterator is referring to. The problem is that you have no way in the current set up to find that position in orig2 and erase it. I can think of several ways to accomplish this, but all are rather complicated. If you used a vector instead of a list it would be much easier. Are you sure you are supposed to use list, not vector?

Unfortunately yes, we have to use a list. Is there a better way to go about finding permutations of values from a list than what I am trying?

Not off the top of my head (except for std::next_permutation of course).

To handle that line with a list, you need a separate variable that remembers where in the original list you are and can find that same place in the copied list and erase it.

Or you need to copy everything in the original list up to the current position first, then copy everything after the current position, without actually copying the value at the current position.

Quote:

---

Or you need to copy everything in the original list up to the current position first, then copy everything after the current position, without actually copying the value at the current position.

---

So instead of trying to use erase() I would basically create two different lists (up to the current iterator, excluding it like you said, then after the current iterator) and then merge those two lists back into one, effectively deleting theIterator?

I searched available list methods and there doesn't seem to be an easy way to split a list?

Quote:

---

To handle that line with a list, you need a separate variable that remembers where in the original list you are and can find that same place in the copied list and erase it.

---

That sounds deceptively simple - I imagine it is not so?

What about using orig2.remove(*theIterator) ? edit: I tried this and it printed out "Processing" about 50 times and nothing else (but no infinite loop).

>> orig2.remove(*theIterator)
*theIterator means the current value pointed to by theIterator. When remove receives a value, it removes all occurrences of that value. If your list doesn't contain any duplicates, that would work. If it does, then that would probably be bad.

>> That sounds deceptively simple - I imagine it is not so?
I wouldn't call it simple. It's just an index. In fact, when your for loop used i, that's what you need. It's just not the best way to work with a list.

>> I searched available list methods and there doesn't seem to be an easy way to split a list?
The constructor of a list can take two iterators. begin() and theIterator will provide the part of the list before the current value. You can then make a copy of theIterator and increment it, then use that and end() to get iterators that cover the second half of the list. Pass those to append or insert or somethiing, and that should work. Still very convoluted.

My list won't ever contain duplicate values - the list will always be a series of unique numbers. So remove should work fine then, correct? Why is it then that when I implemented remove(*theIterator) the output was just 50 "Processing" and nothing else?

For splitting - something like this?

Code:

---

list<int> temp(orig.begin(), theIterator);
list<int>::iterator theIterator2;

for(theIterator2 = theIterator + 1; theIterator2 != orig.end(); theIterator2++)
{
  temp.insert(theIterator2);
}

---

This is what I have now but it is still giving me an infinite loop:

Code:

---

for(theIterator = orig.begin(); theIterator != orig.end(); theIterator++)
        {
        cout << "Processing\n";
        list<int> orig2 = orig;

        list<int> temp(orig.begin(), theIterator);
        list<int>::iterator theIterator2;
        theIterator2 = theIterator++;
        list<int> temp2(theIterator2, orig.end());
        temp.merge(temp2);

        orig2 = temp;

        list<int> perm2 = perm;
               
        perm2.push_back(*theIterator);

        string_permutation(orig2,perm2);

}

---

For anyone interested, the solution turned out to be quite simple really:

Code:

---

iLst routeData::bestRoute(iLst done, iSet left)
{
    int setSize;
    int tempDistance;
    iSetPtr setIterator;
    iSetPtr tempPtr;
    iLstPtr endPtr;
   

    setSize = left.size();

    if(setSize == 0)
    {
        endPtr = done.end();
        endPtr--;
        tempDistance = distance(done) + distance(*endPtr, 1);
        if((tempDistance < shortestDistance) || (shortestDistance == 0))
        {
            shortestDistance = tempDistance;
            finalList = done;
        }

    }

           
    for(setIterator = left.begin(); setIterator != left.end(); setIterator++)
    {
        iLst tempList = done;
        iSet tempSet = left;

        tempSet.erase(*setIterator);
        tempList.push_back(*setIterator);
               
        bestRoute(tempList, tempSet);
           
    }
 
   
    return finalList;
}

---