Logic problems

This is a discussion on Logic problems within the C++ Programming forums, part of the General Programming Boards category; What does this error mean? Code: 25 permutation.cpp invalid conversion from `int' to `std::_List_node_base*' I know I am performing my ...

  1. #16
    Registered User
    Join Date
    Sep 2007
    Posts
    100
    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);
    }

  2. #17
    Registered User
    Join Date
    Jan 2005
    Posts
    7,328
    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.

  3. #18
    Registered User
    Join Date
    Sep 2007
    Posts
    100
    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?
    "I don't fail - I succeed at finding things that don't work"
    Website Promotion Techniques @AbstractPromotion.com

  4. #19
    Registered User
    Join Date
    Jan 2005
    Posts
    7,328
    >> 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?

  5. #20
    Registered User
    Join Date
    Sep 2007
    Posts
    100
    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).
    "I don't fail - I succeed at finding things that don't work"
    Website Promotion Techniques @AbstractPromotion.com

  6. #21
    Registered User
    Join Date
    Jan 2005
    Posts
    7,328
    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?

  7. #22
    Registered User
    Join Date
    Sep 2007
    Posts
    100
    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;
    }
    "I don't fail - I succeed at finding things that don't work"
    Website Promotion Techniques @AbstractPromotion.com

  8. #23
    Registered User
    Join Date
    Jan 2005
    Posts
    7,328
    >> 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?

  9. #24
    Registered User
    Join Date
    Sep 2007
    Posts
    100
    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?
    "I don't fail - I succeed at finding things that don't work"
    Website Promotion Techniques @AbstractPromotion.com

  10. #25
    Registered User
    Join Date
    Jan 2005
    Posts
    7,328
    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.

  11. #26
    Registered User
    Join Date
    Sep 2007
    Posts
    100
    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).
    "I don't fail - I succeed at finding things that don't work"
    Website Promotion Techniques @AbstractPromotion.com

  12. #27
    Registered User
    Join Date
    Jan 2005
    Posts
    7,328
    >> 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.

  13. #28
    Registered User
    Join Date
    Sep 2007
    Posts
    100
    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);
    }
    "I don't fail - I succeed at finding things that don't work"
    Website Promotion Techniques @AbstractPromotion.com

  14. #29
    Registered User
    Join Date
    Sep 2007
    Posts
    100
    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);
    
    }
    "I don't fail - I succeed at finding things that don't work"
    Website Promotion Techniques @AbstractPromotion.com

  15. #30
    Registered User
    Join Date
    Sep 2007
    Posts
    100
    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;
    }
    "I don't fail - I succeed at finding things that don't work"
    Website Promotion Techniques @AbstractPromotion.com

Page 2 of 2 FirstFirst 12
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. No clue how to make a code to solve problems!
    By ctnzn in forum C Programming
    Replies: 8
    Last Post: 10-16-2008, 02:59 AM
  2. Logic Problems
    By mike_g in forum C Programming
    Replies: 3
    Last Post: 08-06-2008, 10:19 AM
  3. Actors, cues, event based logic.
    By Shamino in forum Game Programming
    Replies: 2
    Last Post: 04-27-2006, 10:58 PM
  4. Circular Logic
    By DavidP in forum A Brief History of Cprogramming.com
    Replies: 1
    Last Post: 10-15-2001, 08:10 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21