String Permutation.

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;
    
    vector toret;
    
    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;
}