Thread: Logic problems

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?

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).

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;
}

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?

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?

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).

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;
}