#### Archived

This topic is now archived and is closed to further replies.

# recursive permutation algorithm... am i confused?

This topic is 5928 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hello! I been trying to figure out a recursive algorithm for finding all permutations of a set, but cant seem to get it right! Currently I have:

//*****************************************************************************

//* FILE:		 permutations.cpp

//* AUTHOR:		 Chris McBride

//* DATE:		 26 Aug 02

//* DESCRIPTION: Simple driver program to prun the recursive

//*              permutations function.

//*****************************************************************************

#include <iostream>
#include <string>
#include <vector>

using namespace std;

void permute(const string& str);
void permute(const string& str, int curPos, int swapPos);

int counter = 0;

//*****************************************************************************

//* main

//*

//* This is a driver for the recursive permutation functions found below...

//*****************************************************************************

int main()
{
string userString = "12345";
//cout << "Please enter a random string: ";

//cin  >> userString;

cout << "Now generating all permutations of " << userString << "." << endl;

//* Call non recursive permute function to get the ball rolling...

permute(userString);

cout << "Counter: " << counter << endl;

return 0;
}

//*****************************************************************************

//* Swap

//*

//* simple value swapping function.

//*****************************************************************************

template <class T>
void Swap(T& x, T& y)
{
T temp = x;
x = y;
y = temp;
return;
}

//*****************************************************************************

//* permute

//*

//* This function calls into the recursive function repeatedly in an attempt

//* to generate all the possible permutations.

//*****************************************************************************

void permute (const string& str)
{
int len = str.size();

permute(str, 0, len-1);

return;
}

void permute(const string& str, int low, int high)
{
++counter;

if(low >= high)
{
cout << str << endl;
return;
}

string t(str);

for(int i=low; i<=high; i++)
{
Swap(t[i],t[high]);
permute(t, i+1, high);
Swap(t[i],t[high]);
}

return;
}

Obviously, this code is slightly useless since it doesnt work... BUT, can anyone tell me where Im going wrong with my logic here? Thanks!

##### Share on other sites
Well, you could do it this way...

#include <algorithm>
...
std::next_permutation(v.begin(), v.end());

##### Share on other sites
The recursive call to permute is wrong.

Finding out exactly how is left to the reader as an excercise.

1. 1
Rutin
54
2. 2
3. 3
4. 4
5. 5

• 10
• 28
• 20
• 9
• 20
• ### Forum Statistics

• Total Topics
633412
• Total Posts
3011729
• ### Who's Online (See full list)

There are no registered users currently online

×