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;
    }
}
Comments