# Permutation algorithm using stack

Page 1 of 1

## 6 Replies - 15852 Views - Last Post: 31 July 2009 - 02:59 AMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=33351&amp;s=2c69d1f05b7b7b5da614b90a4b7e6c22&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 knightrider

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

# Permutation algorithm using stack

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

Reputation: 2255
• 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.

### #3 sharan666

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

## Re: Permutation algorithm using stack

Posted 18 September 2007 - 09:23 AM

NickDMax, 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..

### #5 silentfred

Reputation: 2
• 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);}
}
}
}

### #6 mondflustern

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

## Re: Permutation algorithm using stack

Posted 27 July 2009 - 08:26 AM

silentfred, 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

### #7 DarkRanger

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

## Re: Permutation algorithm using stack

Posted 30 July 2009 - 05:35 AM

mondflustern, 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

### #8 silentfred

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

## Re: Permutation algorithm using stack

Posted 31 July 2009 - 02:59 AM

DarkRanger, on 30 Jul, 2009 - 04:35 AM, said:

mondflustern, 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