Permutations of string

Create all  permutations of an input string.  eg:  permutations of "abc" are --  "abc", "acb", "bac", "bca", "cab", "cba"

/*

 * StringPermutations1.cpp

 *

 *  Created on: Apr 18, 2012

 *      Author: Kiran Hegde

 */

#include <iostream>

#include <string>

#include <vector>

#include <string.h>

using namespace std;

void doPermute(string prefix, string rest, vector<string> &output) {

    int len = rest.size();

    if (len == 0) {

        output.push_back(prefix);

    }

    else {

        for (int i=0; i<len; i++)

            doPermute(prefix + rest[i], rest.substr(0, i) + 

                    rest.substr(i+1, len - (i+1)), output);

    }

}

void permute(string input, vector<string> &output) {

    doPermute(string(""), input, output);

}

/**

 * Test the code

 */

int main() {

    string input("abcd");

    vector<string> perms;

    permute(input, perms);

    cout << "Permutations: " << endl;

    for (unsigned int i=0; i<perms.size(); i++) {

        cout << perms[i] << endl;

    }

    return 0;

}