Thread: Programming Challenge: Permutations

  1. #1
    Registered User
    Join Date
    Sep 2011
    Posts
    3

    Programming Challenge: Permutations

    My question refers to the Programming Challenge section of the website wherein one of the challenges is about determining the Permutations of a string. That solution of that program has me pulling my hair. It is a recursive algorithm. For an input string "cat", once "cat" and "cta" have been printed out, the value of variable "place" turns out to be 3. At that instance, the function should terminate as the for loop does not support values equal or greater than 3. By some sort of miracle, however, the value of variable place is 1 (I put a cout statement inside the for loop). How in the world can "place" possibly be 1 after it has been 2. There is nothing that decrements place.

  2. #2
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    You didn't post the code in question, but consider this:
    Code:
    function foo( arg )
        if arg > 0
            foo arg -1
        output arg
    You call the function with some value, and as long as your argument is greater than 0, it recursively calls itself. Then when it returns from that, it prints that value (or if the if fails, and it skips recursion). So:
    Code:
    foo 3
        foo 2
            foo 1
                foo 0
                    prints 0
                prints 1
            prints 2
        prints 3

    Quzah.
    Hope is the first step on the road to disappointment.

  3. #3
    Registered User
    Join Date
    Sep 2011
    Posts
    3
    Code:
    #include <iostream>
    #include <string>
    
    using namespace std;
    
    string swtch(string topermute, int x, int y)
    {
    	string newstring = topermute;
    	newstring[x] = newstring[y];
    	newstring[y] = topermute[x]; //avoids temp variable
    	return newstring;
    }
    void permute(string topermute, int place)
    {
    	if(place == topermute.length() - 1)
    	{
    		cout << topermute << endl;
    	}
    	for(int nextchar = place; nextchar < topermute.length(); nextchar++)
    	{
    		cout << place << endl; //how can place be 1 after being 2. it is never decremented. 
    		permute(swtch(topermute, place, nextchar), place+1);
    	}
    }
    
    int main()
    {
    		string str = "cat";
            permute(str, 0);
    }

  4. #4
    Registered User rogster001's Avatar
    Join Date
    Aug 2006
    Location
    Liverpool UK
    Posts
    1,472
    Well maybe it's you are passing copies of place into the function, thus when you escape from one of the recursive calls then you are starting again with the place as its value was at that level, something like that, i not really looked into it.
    Thought for the day:
    "Are you sure your sanity chip is fully screwed in sir?" (Kryten)
    FLTK: "The most fun you can have with your clothes on."

    Stroustrup:
    "If I had thought of it and had some marketing sense every computer and just about any gadget would have had a little 'C++ Inside' sticker on it'"

  5. #5
    Registered User
    Join Date
    Sep 2011
    Posts
    3
    If that were true, then the value of place should be zero (as that is what it initially started out with). The fact that it's 1 has baffled me.

  6. #6
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Have you tried tracing the code? You may need to write down the state of the stack for the current function call in order to keep your sanity, unless you have a good memory.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  7. #7
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Left column is the first call, second column is a recursive call. Each has it's own loop over it's own copy of the place variable...
    Code:
    0
        0
        1
        2 // Now it's a 2
    1     // and now it's a 1
        0
        1
        2
    2
        0
        1
        2
    Does it make sense yet?
    Last edited by iMalc; 09-09-2011 at 03:47 AM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  8. #8
    Registered User rogster001's Avatar
    Join Date
    Aug 2006
    Location
    Liverpool UK
    Posts
    1,472
    I ran in the debugger stepping through carefully, one problem i think you have is there is no clearly defined exit condition for the recursion, but in any case it works with the for loop, so: The recursion goes on until place reaches a value of 3, the for loop is then skipped, then you exit out to where the value of place was 2, i would then have expected to step back into the for loop but it is again skipped, and this i dont know why, but the net effect is that you exit back out of the recursion again to where place = 1, this is what you are seeing output, am checking again with the call stack
    Thought for the day:
    "Are you sure your sanity chip is fully screwed in sir?" (Kryten)
    FLTK: "The most fun you can have with your clothes on."

    Stroustrup:
    "If I had thought of it and had some marketing sense every computer and just about any gadget would have had a little 'C++ Inside' sticker on it'"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Beginners C Programming Challenge
    By UCnLA in forum C Programming
    Replies: 2
    Last Post: 03-18-2008, 12:15 PM
  2. Programming challenge
    By sybariticak47 in forum Windows Programming
    Replies: 1
    Last Post: 01-05-2006, 02:14 AM
  3. Programming Challenge (for my school)
    By Ezerhorden in forum C++ Programming
    Replies: 2
    Last Post: 01-04-2006, 06:56 AM
  4. programming challenge
    By grohyt in forum C++ Programming
    Replies: 3
    Last Post: 09-19-2005, 07:07 PM
  5. C programming challenge
    By lost in C in forum C Programming
    Replies: 6
    Last Post: 03-11-2002, 01:27 AM

Tags for this Thread