Problem creating a recursive string permutation function

This is a discussion on Problem creating a recursive string permutation function within the C++ Programming forums, part of the General Programming Boards category; I'm given a string that I need to find all permutations of, the thing is I'm restricted to calling it ...

  1. #1
    Ethernal Noob
    Join Date
    Nov 2001
    Posts
    1,901

    Problem creating a recursive string permutation function

    I'm given a string that I need to find all permutations of, the thing is I'm restricted to calling it recursively and it returning void, taking only one string parameter:
    Code:
    void permute(string& word);
    The thing Is I just can't work out why it can be recursive. I would understand if it took another parameter, possibly int fact, which would be the n! which is how many times it would need to call itself, reaching a base case that:

    Code:
    if(fact == 0)
       return
    else
    {
       permute(word, n-1)
       //do the permutation routine
    }
    I've figured out a routine to do the permutation, which is just moving around a substring of the words exluding the first, then just going down the word, but I'm restricted to using one parameter. Maybe I'm just not good at the recursion.

  2. #2
    Registered User SKeane's Avatar
    Join Date
    Sep 2006
    Location
    England
    Posts
    234
    What about taking each character in the string and recursively calling the function on the remaining characters, until you call the function with only one character (this ends the recursion).

  3. #3
    Ethernal Noob
    Join Date
    Nov 2001
    Posts
    1,901
    I was able to get the first line of permutations, but If i recursively "shrink" the string, I will not be able to display the letter of the previous string that would make the permutation for each letter being the first of the string

    Code:
    /*
    function prints all permutations of the given string, 
    recursively calls itself
    */
    void permute(string& str)
    {
    	string next = str;
    	
    	if(str.length() == 1)
    	{
    		cout << str << endl;
    		return;
    	}
    	else
    	{
    		for(string::size_type i = 0; i < next.length(); ++i)
    		{
    			cout << next << endl;
    			next = next.substr(1) + next[0];
    		}
    		next = next.substr(1);
    		permute(next);
    	}
    }
    Edit, bah that doesn't work, disregard.
    Last edited by indigo0086; 10-10-2006 at 08:20 AM.

  4. #4
    Registered User SKeane's Avatar
    Join Date
    Sep 2006
    Location
    England
    Posts
    234
    I take it you can't use the STL function?

  5. #5
    Ethernal Noob
    Join Date
    Nov 2001
    Posts
    1,901
    I think it needs to be from the ground up using at most the string member functions like substr and such.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 6
    Last Post: 04-21-2006, 09:49 PM
  2. <Gulp>
    By kryptkat in forum Windows Programming
    Replies: 7
    Last Post: 01-14-2006, 01:03 PM
  3. Problem with Visual C++ Object-Oriented Programming Book.
    By GameGenie in forum C++ Programming
    Replies: 9
    Last Post: 08-30-2005, 12:21 AM
  4. c++ linking problem for x11
    By kron in forum Linux Programming
    Replies: 1
    Last Post: 11-19-2004, 10:18 AM
  5. Replies: 5
    Last Post: 02-08-2003, 07:42 PM

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