Permutations of string

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

Solution :

1. We first list the combinations using recursive procedure by selecting or not selecting characters until K length has been formed
2. The for each combination we permute them using another recursive procedure

Complexity :

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

Code :

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();
    }
}