[ishkabible]

Ok so the goal of this challenge is to write a function that takes a string and returns a sequence of all possible permutations.

So for example if I had the string "ab" then the sequence ["ab", "ba"] would be returned.

here is a Wikipedia link on permutations.

Here is a bigger example, If I have the string "ish" then I would have the following permutations

ish
ihs
shi
sih
his
hsi

I found this tool for generating the permutations, that way you can check it.

And for extra kudos don't use the C++ standard library for finding the permutations
For those of who are less familiar with the C++ stranded library have a look at the algorithm library.

Here is a good function prototype to use, you can make it what ever you want though.

void P(std::vector<std::string>& perms, std::string str);

Also one last thing, please use spoiler tags when posting solutions. that way everyone can have a fair chance at coming up with there own solution.

[ spoiler] [ /spoiler]

Spoiler

And most importantly, have fun!!

once the challenge gets going some more, ill post my two solutions. one using the standard library and the other without.

[KYA]

Spoiler

http://www.dreaminco...snippet2232.htm

/*
 * KYA
 * String Permutation
 * @ params: char array, begin, and end of array
 * 7-21-08
 */

#include <iostream>
#include <string>
using namespace std;

void swap(char* first, char* second)
{
        char ch = *second;
        *second = *first;
        *first = ch;
}

int permute(char* set, int begin, int end)
{
        int i;
        int range = end - begin;
        if (range == 1) {
                cout << set << endl;
        } else {
                for(i=0; i<range; i++) {
                        swap(&set[begin], &set[begin+i]);		//initial swap
                        permute(set, begin+1, end);				//recursion
                        swap(&set[begin], &set[begin+i]);       //swap back
                }
        }
        return 0;
}

//Example Implementation -- Up to you on how to use
int main()
{
        char str[255]; //string 
	cout << "Please enter a string: ";
	cin.getline(str, 255); //take string
        permute(str, 0, strlen(str)); //permutate the string
        return 0;
}

[ishkabible]

very nice!! kudos for doing it with out the standard library!!

[ishkabible]

ok, here's my two solutions. in my non-std one i still used std::vector and std::string but it's in the heart of what i meant.

Spoiler

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

inline unsigned int fac(unsigned int x) {
	unsigned int total = 1;
	for(;x;--x) {
		total *= x;
	}
	return total;
}

void P1(std::vector<std::string>& perms, std::string str) {
	std::sort(str.begin(),str.end());
	perms.reserve(fac(str.size()));
	perms.push_back(str);
	while(std::next_permutation(str.begin(),str.end())) {
		perms.push_back(str);
	}
}

void P2(std::vector<std::string>& perms, std::string str, std::string s="") {
	int size = str.size();
	if(size) {
		for(int i=0;i<size;++i) {
			P2(perms, str.substr(0, i) + str.substr(i+1, size), s+str[i]);
		}
	} else {
		perms.push_back(s);
	}
}

int main() {
    std::vector<std::string> perms;
	P1(perms, "is");
    for(unsigned int i=0;i<perms.size();++i) {
		std::cout<<perms[i]<<std::endl;
    }
    perms.clear();
	P2(perms, "is");
    for(unsigned int i=0;i<perms.size();++i) {
		std::cout<<perms[i]<<std::endl;
    }
    return 0;
}

[RevTorA]

This was fun actually. I've never gotten to use this method before hehe. Not the fastest implementation however.

Spoiler

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

using namespace std;

void GetPermutation(vector<string> &perms, string str, string remaining)
{
	//If we've reached the last letter in this permutation, add the new perm
	//to our permutations list
	if(remaining.length() == 1)
	{
		string permutation = str + remaining;
		perms.push_back(permutation);
	}
	else
	{
		//Otherwise, go through each of the remaining letters in the permutation
		for(unsigned int i = 0; i < remaining.length(); i++)
		{
			//Our next starting string is the current string + the next character permutation
			string newString = str;
			newString += remaining[i];

			//Then we fill newRemaining with the rest of the characters
			string newRemaining = "";
			for(unsigned int j = 0; j < remaining.length(); j++)
			{
				if(j != i)
					newRemaining += remaining[j];
			}

			//And cue recursive function call
			GetPermutation(perms, newString, newRemaining);
		}
	}
}

int main(int argc, char* argv[])
{
	string str;

	cout << "String to find permutations of: ";
	cin >> str;

	vector<string> perms;
	GetPermutation(perms, "", str);

	cout << endl << " Permutations:" << endl;
	cout << "---------------------" << endl;

	for(unsigned int i = 0; i < perms.size(); i++)
	{
		cout << perms[i] << endl;
	}

	cout << "There were " << perms.size() << " Permutations.";

	cin.ignore();
	getchar();
}

Now to check out the other solutions.

Edit: Looks like I was mostly in line with everyone else... Mine's longer though, I probably didn't think it through enough. Was fun anyway

Edit2: I'm also really proud of myself because my code worked perfectly the first time I ran it... Not a huge program, but still. How often does that happen to you guys? XD

Edit3: 4 1/2 minutes to calculate and print all 362880 permutations from a 9 letter word... Do I dare try 10? lol. Guess that's why recursion isn't used very often

This post has been edited by RevTorA: 16 May 2011 - 09:34 AM

[sarmanu]

Spoiler

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

bool IsValid(std::vector<size_t> const &Indexes, const size_t &MaxIndex)
{
	for (size_t i = 1; i <= MaxIndex - 1; i++)
		if (Indexes.at(i) == Indexes.at(MaxIndex))
			return false;

	return true;
}

void Write(const std::vector<size_t> &Indexes, const std::string &Word)
{
	for (size_t i = 0; i < Word.length(); i++)
		std::cout << Word[Indexes[i + 1] - 1];
	std::cout << std::endl;
}

void Generate(const std::string &StartingWord)
{
	size_t Index = 1, Len = StartingWord.length();

	std::vector<size_t> Indexes;
	Indexes.resize(Len + 1);
	for (size_t i = Index; i <= Len; i++)
		Indexes[i] = 0;

	while (Index > 0)
	{
		if (Index == Len + 1)
		{
			Write(Indexes, StartingWord);
			Index--;
		}
		else
		{
			if (Indexes[Index] <= Len - 1)
			{
				Indexes[Index]++;
				if (IsValid(Indexes, Index))
					Index++;
			}
			else
			{
				Indexes[Index] = 0;
				Index--;
			}
		}
	}
}

int main()
{
	std::string starting = "ish";
	Generate(starting);

	return 0;
}

And without STL, not that much of a difference except the need of messy dynamic memory allocation:

Spoiler

#include <iostream>
#include <string>

bool IsValid(size_t const Indexes[], const size_t &MaxIndex)
{
	for (size_t i = 1; i <= MaxIndex - 1; i++)
		if (Indexes[i] == Indexes[MaxIndex])
			return false;

	return true;
}

void Write(size_t const Indexes[], const char *Word)
{
	for (size_t i = 0; i < strlen(Word); i++)
		std::cout << Word[Indexes[i + 1] - 1];
	std::cout << std::endl;
}

void Generate(const char *StartingWord)
{
	size_t Index = 1, Len = strlen(StartingWord);

	size_t *Indexes = new size_t[Len + 1];
        Indexes[0] = 0;
	for (size_t i = Index; i <= Len; i++)
		Indexes[i] = 0;

	while (Index > 0)
	{
		if (Index == Len + 1)
		{
			Write(Indexes, StartingWord);
			Index--;
		}
		else
		{
			if (Indexes[Index] <= Len - 1)
			{
				Indexes[Index]++;
				if (IsValid(Indexes, Index))
					Index++;
			}
			else
			{
				Indexes[Index] = 0;
				Index--;
			}
		}
	}
	delete [] Indexes;
}

int main()
{
	char starting[] = "ish";
	Generate(starting);

	return 0;
}

This post has been edited by sarmanu: 17 May 2011 - 08:57 AM

[ishkabible]

i like a lot, it's non-recursive! i couldn't think of a non recursive way
i didn't think to generate the permutations as indexes rather than stirngs

[RetardedGenius]

I wrote this a few weeks ago to improve my understanding of permutations and combinatorics. I've subsequently used it solve several of the Project Euler problems.

Unfortunately my code generates all of the permutations for an array of integers, as opposed to a string; the concept however is identical, so I hope that this is OK?

Spoiler

#include <iostream>
#include <cstdio>  // for printf()
using namespace std;

void PrintArray(int[], int);

int main()
{
    const int length = 4;
    int a[length] = { 1, 2, 3, 4};
    int k, l;

    while (true)
    {
        PrintArray(a, length);

        k = -1;
        l = -1;

        // Find the largest index k such that a[k] < a[k + 1].
        for (int i = 0; i < length - 1; i++)
            if (a[i] < a[i + 1] && i > k)
                k = i;

        if (k == -1)
        {
            printf("Last permutation\n");
            break;
        }

        // Find the largest index l such that a[k] < a[l].
        for (int i = 0; i < length; i++)
            if (a[k] < a[i] && i > l)
                l = i;

        swap(a[k], a[l]);

        // Reverse the sequence from a[k + 1] up to and including the final element a[n].
        for (int i = 0; i < (length - (k+1)) / 2; i++)
            swap(a[i + (k+1)], a[length - 1 - i]);
    }

    return 0;
}
void PrintArray(int ary[], int length)
{
    for (int i = 0; i < length; i++)
        printf("%i", ary[i]);
    printf("\n");
}

[ishkabible]

nice, ive only solved 12 of the project Euler problems. i might pick that up again some time

[RetardedGenius]

ishkabible, on 17 May 2011 - 11:46 PM, said:

nice, ive only solved 12 of the project Euler problems. i might pick that up again some time

They're great fun, I finished my 50^th today.
As coincidence would have it I started a topic about Project Euler earlier today, here.

[ishkabible]

you know if you could stuff that code into a function with templates it would not just apply to arrays of integers but rather to any container whose elements support the '=' operator.

and if you used the copy constructor instead it would apply to any copyable data type.

new ((void*)&a[i]) T(x);

this explicitly calls the copy constructor without allocating new space. it has to be one of weirdest syntaxs ever but it works never the less.

This post has been edited by ishkabible: 18 May 2011 - 05:59 AM

[RetardedGenius]

That's a cool idea, I was aware that that is possible, although I am not sure that my C++ knowledge is quite ready for that. I will definitely encapsulate it into a function with templates at some point though, I will post it as snippet as well.

[CTphpnwb]

I just saw this topic and was going to write this, but look what I found in my miscellaneous code folder:

Spoiler

#include<iostream>
#include<vector>

using namespace std;
vector<string> permute(string);
vector<string> inserteverywhere(string, vector<string>);

int main () {
	string mystring = "abcde";
	vector<string>allstrings;
	allstrings = permute(mystring);
	for (int i = 0; i < allstrings.size(); i++) {
		cout << allstrings[i] << endl;
	}
	cout << allstrings.size() << endl;
	return 0;
}

vector<string> permute(string st)
{
	vector<string> thestrings;
	vector<string> permuted;
	if (st.length() == 1) {
		thestrings.push_back(st);
	} else {
		permuted = permute(st.substr(1));
		thestrings = inserteverywhere(st.substr(0, 1), permuted);
	}
	return thestrings;
}

vector<string> inserteverywhere(string ch, vector<string> perms)
{
	vector<string> myperms;
	for (int i = 0; i < perms.size(); i++) {
		for (int j = 0; j < perms[i].length(); j++) {
			myperms.push_back(perms[i].substr(0,j)+ch+perms[i].substr(j));
		}
		myperms.push_back(perms[i]+ch);
	}
	return myperms;
}

Not sure when I wrote it.

Sorry about the tags. I was just about to fix it!

This post has been edited by CTphpnwb: 18 May 2011 - 04:29 PM
Reason for edit:: please use spoiler tags when posting code for a challnge

[ishkabible]

spoiler tags please

[Karel-Lodewijk]

There is a std::next_permutation in the algorithm header, that makes the stdlib version fairly trivial.

Spoiler

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

int main() {
    std::string str = "ish";
    std::sort(str.begin(), str.end());
    do
        std::cout << str << std::endl;
    while (std::next_permutation(str.begin(), str.end()));
}

Edit: wait, nm, ishkabible seems to have used it.

This post has been edited by Karel-Lodewijk: 13 January 2012 - 02:28 AM