Permutation algorithm using stack

Converting a recusive algorithm to use a stack

Page 1 of 1

6 Replies - 10094 Views - Last Post: 31 July 2009 - 02:59 AM Rate Topic: -----

#1 knightrider  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 5
  • Joined: 15-September 07

Permutation algorithm using stack

Post icon  Posted 15 September 2007 - 08:05 PM

Hi,
I have an assignment to implement a nonrecursive permutation algorithm using a stack ADT. The explanation to the problem includes a recursive algorithm that I don't understand:

  
#include <iostream>
#include <vector>

using namespace std;

void gen(vector<int> & permutation, int level, int n)	//What is the function of the 'level' variable?
{
	int i;
	if(level==n)
	{
		for(i=0;i<n;i++)
			cout<<permutation[i];
		cout<<endl;
	}
	else
	{
		for(i=0;i<=level;i++)
		{
			vector<int>  p(permutation);   //What does this do?
			p.insert(p.begin()+i,level);	  //And what is happening here?
			gen(p,level+1,n);
		}
	}
}

int main()
{
	int n;
	cin>>n;

	vector<int> permutation;
	gen(permutation,0,n);
	return 0;
}



I've put the things that I don't understand as notes in the code.

I would also appreciate it if someone could help me how to begin with the problem. I've implemented my own stack ADT but don't know how to go about the problem proper. I also don't understand how to use stack in the algorithm.

Any help is much appreciated!

Is This A Good Question/Topic? 0
  • +

Replies To: Permutation algorithm using stack

#2 NickDMax  Icon User is offline

  • Can grep dead trees!
  • member icon

Reputation: 2250
  • View blog
  • Posts: 9,245
  • Joined: 18-February 07

Re: Permutation algorithm using stack

Posted 16 September 2007 - 09:31 AM

Ok question #1 "//What is the function of the 'level' variable?"

Level is a marker. To understand its purpose you really need to run the algorithm in your head (or on paper) a few times.

#2 "vector<int> p(permutation); //What does this do?"

This creates a copy of the current permutation (vector). This way the next call to the gen function will not interfere with the current permutation.

#3 "p.insert(p.begin()+i,level); //And what is happening here?"

This inserts a number "level" into the new vector.


So. Lets run this though our head with n=4. our current vactor will be v(#, #, #, #) -- so V() is empty, and V(1) has one number V(1, 2) has two numbers etc.

Gen(V(), 0, 3)
	Gen(V(1), 1, 3) (level==1 So there will only be 1 loop at this level)
		Gen(V(2, 1), 2, 3) (Level==2 so there will be 2 loops at this level)
			Gen(V(3, 2, 1), 3, 3) (Level=3 so there will be 3 loops at this level)
				level == n: Print 3, 2, 1
			Gen(V(2, 3, 1), 3, 3) 
				level == n: Print 2, 3, 1
			Gen(V(2, 1, 3), 3, 3)
				level == n: Print 2, 1, 3
		Gen(V(1, 2), 2, 3)
			Gen(V(3, 1, 2), 3, 3) (Level=3 so there will be 3 loops at this level)
				level == n: Print 3, 1, 2
			Gen(V(1, 3, 2), 3, 3)
				level == n: Print 1, 3, 2
			Gen(V(1, 2, 3), 3, 3)
				level == n: Print 1, 2, 3
	  
All permutations have been printed!!


Try running though it a few times by yourself.

Once you understand the algorithm, it is not very hard to add a stack in place of the recursion.
Was This Post Helpful? 0
  • +
  • -

#3 sharan666  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 1
  • Joined: 18-September 07

Re: Permutation algorithm using stack

Posted 18 September 2007 - 09:23 AM

View PostNickDMax, on 16 Sep, 2007 - 09:31 AM, said:

Ok question #1 "//What is the function of the 'level' variable?"

Level is a marker. To understand its purpose you really need to run the algorithm in your head (or on paper) a few times.

#2 "vector<int> p(permutation); //What does this do?"

This creates a copy of the current permutation (vector). This way the next call to the gen function will not interfere with the current permutation.

#3 "p.insert(p.begin()+i,level); //And what is happening here?"

This inserts a number "level" into the new vector.


So. Lets run this though our head with n=4. our current vactor will be v(#, #, #, #) -- so V() is empty, and V(1) has one number V(1, 2) has two numbers etc.

Gen(V(), 0, 3)
	Gen(V(1), 1, 3) (level==1 So there will only be 1 loop at this level)
		Gen(V(2, 1), 2, 3) (Level==2 so there will be 2 loops at this level)
			Gen(V(3, 2, 1), 3, 3) (Level=3 so there will be 3 loops at this level)
				level == n: Print 3, 2, 1
			Gen(V(2, 3, 1), 3, 3) 
				level == n: Print 2, 3, 1
			Gen(V(2, 1, 3), 3, 3)
				level == n: Print 2, 1, 3
		Gen(V(1, 2), 2, 3)
			Gen(V(3, 1, 2), 3, 3) (Level=3 so there will be 3 loops at this level)
				level == n: Print 3, 1, 2
			Gen(V(1, 3, 2), 3, 3)
				level == n: Print 1, 3, 2
			Gen(V(1, 2, 3), 3, 3)
				level == n: Print 1, 2, 3
	  
All permutations have been printed!!


Try running though it a few times by yourself.

Once you understand the algorithm, it is not very hard to add a stack in place of the recursion.


Good job on the explanation, minor correction : the permutations printed will be from 0 to N-1 therefore it will be 0,1,2 etc..
Was This Post Helpful? 0
  • +
  • -

#5 silentfred  Icon User is offline

  • New D.I.C Head

Reputation: 2
  • View blog
  • Posts: 2
  • Joined: 26-July 09

Re: Permutation algorithm using stack

Posted 26 July 2009 - 02:58 AM

I got the same project.Use the following functions together and you will be fine.
Use the "swapChars" function to swop the characters.


/*
A possible helper function to swap characters
in a given string.
*/
void swapChars(string* s, int j, int i)
{
char tmp = (*s)[i];
(*s)[i] = (*s)[j];
(*s)[j] = tmp;
}



/*
This function takes a string pointer to the string of which
all permutations are to be generated and pushes each permutation
onto the stack given as a parameter iteratively.
*/
void permuteIterate(string* c,stack<string>* s)
{
for (int x = 0; x < 3; x++) //change 3 to 'n' if you would like a custom size string
{
for (int y = 0; y< 3; y++) //change 3 to 'n' if you would like a custom size string
{
if (y != x){
swapChars(c,x,y);
(*s).push(*c);}
}
}
}
Was This Post Helpful? 1

#6 mondflustern  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 1
  • Joined: 17-May 09

Re: Permutation algorithm using stack

Posted 27 July 2009 - 08:26 AM

View Postsilentfred, on 26 Jul, 2009 - 01:58 AM, said:

I got the same project.Use the following functions together and you will be fine.
Use the "swapChars" function to swop the characters.


/*
A possible helper function to swap characters
in a given string.
*/
void swapChars(string* s, int j, int i)
{
char tmp = (*s)[i];
(*s)[i] = (*s)[j];
(*s)[j] = tmp;
}



/*
This function takes a string pointer to the string of which
all permutations are to be generated and pushes each permutation
onto the stack given as a parameter iteratively.
*/
void permuteIterate(string* c,stack<string>* s)
{
for (int x = 0; x < 3; x++) //change 3 to 'n' if you would like a custom size string
{
for (int y = 0; y< 3; y++) //change 3 to 'n' if you would like a custom size string
{
if (y != x){
swapChars(c,x,y);
(*s).push(*c);}
}
}
}



hey silentfred!
you almost got the idea i want to use...

how did you do it recursively using the same signature

void recursive(string* str, stack<string> stckStr)?

this could really help!

thanks
Was This Post Helpful? 0
  • +
  • -

#7 DarkRanger  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 1
  • Joined: 30-July 09

Re: Permutation algorithm using stack

Posted 30 July 2009 - 05:35 AM

View Postmondflustern, on 27 Jul, 2009 - 07:26 AM, said:

hey silentfred!
you almost got the idea i want to use...

how did you do it recursively using the same signature

void recursive(string* str, stack<string> stckStr)?

this could really help!

thanks


Luckily for you silentfred attends the same university as me, so I also did this part of the practical excersize. Anyway, here goes:

int start = 0; //Putting this in the method generates a segmentation fault
void permuteRecursive(string* string, stack<string>* s)
{
	int length = string->length();
	int range = length - start;

	if (range == 0)
	{
		s -> push(*string);
	}
	else
	{
		for(int k = 0; k < range; k++)
		{
			swapChars(string, start, start+k);
			start++;
			permuteRecursive(string,s);
			start--;
			swapChars(string, start, start+k);
		}
	}
}

This post has been edited by DarkRanger: 30 July 2009 - 05:43 AM

Was This Post Helpful? 0
  • +
  • -

#8 silentfred  Icon User is offline

  • New D.I.C Head

Reputation: 2
  • View blog
  • Posts: 2
  • Joined: 26-July 09

Re: Permutation algorithm using stack

Posted 31 July 2009 - 02:59 AM

View PostDarkRanger, on 30 Jul, 2009 - 04:35 AM, said:

View Postmondflustern, on 27 Jul, 2009 - 07:26 AM, said:

hey silentfred!
you almost got the idea i want to use...

how did you do it recursively using the same signature

void recursive(string* str, stack<string> stckStr)?

this could really help!

thanks


Luckily for you silentfred attends the same university as me, so I also did this part of the practical excersize. Anyway, here goes:

int start = 0; //Putting this in the method generates a segmentation fault
void permuteRecursive(string* string, stack<string>* s)
{
	int length = string->length();
	int range = length - start;

	if (range == 0)
	{
		s -> push(*string);
	}
	else
	{
		for(int k = 0; k < range; k++)
		{
			swapChars(string, start, start+k);
			start++;
			permuteRecursive(string,s);
			start--;
			swapChars(string, start, start+k);
		}
	}
}






Shot!Some good code there DarkRanger!!Mine is similar but had problems when i wanted to use more than 3 characters.Im pretty much a noob but try and work the discrete maths and calculus to make up for it...NOT WORKING!!!Peace
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1