Archived

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

recursive permutation algorithm... am i confused?

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

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites