## Thursday, March 27, 2014

### 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