Permutations of string - k at a time

Implement permutation of a string of length N with K letters chosen at a time (N > K).  Eg:  Permutation of "abc" with 2 letters chosen at a time are - ab, ac, ba, bc, ca, cb

/*

 * StringPermutationsWithSize.cpp

 *

 *  Created on: Apr 18, 2012

 *      Author: kiran

 */

#include <iostream>

#include <string>

#include <vector>

#include <string.h>

using namespace std;

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

    if (k == 0) {

        output.push_back(prefix);

    }

    else {

        int len = rest.size();

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

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

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

    }

}

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

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

}

/**

 * Test the code

 */

int main() {

    string inp("abc");

    vector<string> perms;

    permute(inp, 2, perms); //choose 2 at at time

    cout << "Permutations: " << perms.size() << endl;

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

        cout << perms[i] << endl;

    }

}