Permutations of every subset of size K

Problem

Given a array of characters of size N. Devise an algorithm to generate all possible permutations of given size K (K <= N).

Solution

Method 1 - Append characters till the length K is reached
We first list the combinations using recursive procedure by selecting or not selecting characters until K length has been formed The for each combination we permute them using another recursive procedure

Time : O(N!)
Space : O(N!) when storing results O(1) if directly output the result

Code in c:

void swap (char \*x, char \*y)  
{  
    char temp;  
    temp = \*x;  
    \*x = \*y;  
    \*y = temp;  
}  
void select(char \*input, int start, int N, char \*selection, int length, int K, stack<string> &combinations){  
    if(start <= N){  
        if(length == K){  
            selection\[length\] = '\\0';  
            combinations.push(string(  
selection));  
        }  
        else {  
            select(input, start + 1, N, selection, length, K, combinations);  
            selection\[length\] = input\[start\];  
            select(input, start + 1, N, selection, length + 1, K, combinations);  
        }  
    }  
}  
  
void permute(char \*input, int index, int N, stack<string> &permutations)  
{  
   if (index == N)  
        permutations.push(string(input));  
   else  
   {  
        for (int i = index; i < N; i++)  
       {  
            swap(input + index, input + i);  
            permute(input, index + 1, N, permutations);  
            swap(input + index, input + i);  
        }  
   }  
}  
  
void all\_permutations(char \*input, int K, stack<string> &permutations){  
    int N = strlen(input);  
    stack<string> combinations;  
    char \*selection = new char\[K+1\];  
    char \*temp = new char\[K+1\];  
     
    select(input, 0, N, selection, 0, K, combinations);  
    while(!combinations.empty()){  
        strcpy(temp, combinations.top().c\_str());  
        permute(temp, 0, K, permutations);  
        combinations.pop();  
    }  
}

Reference -
http://algorithmsforever.blogspot.in/2011/11/permutations-of-string.html

See also