Problem creating a recursive string permutation function

**indigo0086** · 10-10-2006

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.

**SKeane** · 10-10-2006

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

**indigo0086** · 10-10-2006

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.

**SKeane** · 10-10-2006

I take it you can't use the STL function?

**indigo0086** · 10-10-2006

I think it needs to be from the ground up using at most the string member functions like substr and such.

Thread: Problem creating a recursive string permutation function

Thread Tools

Search Thread

Display

Problem creating a recursive string permutation function

Similar Threads

string not fully outputted when a type bool function is called.

<Gulp>

Problem with Visual C++ Object-Oriented Programming Book.

c++ linking problem for x11

Didn't quite know where to post this.......compiler problem...