**I Have Been Working On This**

__Forever__First: String permutation is finding every possible combination of the letters in a string. For example:

-----------

string = "abc"

permutations:

abc

acb

bac

bca

cab

cba

----------

I have had a

**ton**of fun with this, essentially I knew there were solutions available, and I'm sure there are a lot of

*better*solutions as well. However, here's what I came up with.

Step 1. Write a function to swap two characters.

Step 2. Write a recursive function to return all permutations of a given string. It will call itself (minus the) first letter.

**-1-**

string getstringwithswappedchars(int first, int second, string toswap){ char buf = toswap[first]; toswap[first] = toswap[second]; toswap[second] = buf; return toswap; }

**-2-**

I was lying in bed, attempting to sleep, and *pop* I knew how to do it! My solution is essentially this. Take the previous call in the recursive loop (down to one letter which shall return itself) append the current letter to each, then add yourself to a vector after switching the current letter with every single letter in each permutation.

**beautiful**

vector <string> permute(string toperm){ cout << "\npermuting " << toperm; vectortoret; if (toperm.size() <= 1){ toret.push_back(toperm); return toret; } vector tvect = permute(toperm.substr(1,toperm.size()-1)); for (int b = 0; b < tvect.size(); b++){ for (int a = 0; a < toperm.size(); a++){ toret.push_back(getstringwithswappedchars(0,a,toperm[0] + tvect[b])); } } return toret; }

I will admit that is pretty brilliant, quite clean cut as well

ReplyDelete