Microsoft Internship Written Test – Permutation

Question

Write a function that takes a string as argument and generate all its permutations. The prototype is:

void permute(char *);

Logic

Recursion (Suggested by Parminder)

The first logic that comes to mind is, generate the permutation using a recursive function. Now this has got a problem, “How do we keep track of depth of recursion?” The answer is declare a static variable for each of the argument we used to pass. So, one static array for answer and one static integer for depth. Now, we can write normal function and that will generate all permutations, but again the problem is, “What do we do if there is repeatation?” The solution and the program (code) for this logic is left to the reader.

Non Recursive

Since, the given input is a string, another logic is to first sort the string. This will make it the lexicographically smallest string. Next we keep on generating the next largest permutation in lexicographic order. So, if the input is aabb, our program will generate:

aabb
abab
abba
baab
baba
bbaa

Now, to generate the next largest permutation, we need to find the last occurance where a_j is less than a_j+1, where a_j represents the j^th character in the string. Having done that, we need the smallest character greater than a_j and that is to its right. Since, all characters after a_j are in descending order, the first character from right that is greater than a_j will be the required character. Let this character be a_k. Now we swap a_j and a_k and then reverse the string from a_j+1 to the end (This sorts the part from a_j to the end, excluding a_j)

Code (Only non recursive)

I’ll be dividing the program into functions, but in the paper you had to write it in a single one. Also, I’ll be using qsort to sort the array.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare(const void *a, const void *b) {
    return *(char *)a - *(char *)b;
}

void permute(const char * str) {
    char * temp = (char *)malloc(sizeof(char)
                    * strlen(str) + 1);
    strcpy(temp,str);
    qsort(temp,strlen(temp),sizeof(char),compare);
    do {
        printf("%s\n",temp);
    }
    while(next_permutation(temp));
}

int next_permutation(char * a) {
    /* Computing string length and
       checking if it is the last permutation */
    int n = 0;
    int is_last = 1;
    while(a[n])
    {
        // It is not completely non-ascending
        if(a[n] < a[n+1])
            is_last = 0;
        ++n;
    }
    --n; // a[n] is the last character

    /* If it is the last permutation, exit */
    if(is_last)
        return 0;

    /* Find last element a[j] < a[j+1] */
    int j = n - 1;
    while(a[j] >= a[j+1])
        --j;

    /* Find the smallest integer a[k]
       greater a[j], but to its right */
    int k = n;
    while(a[j] >= a[k])
        --k;

    /* Swap a[j] and a[k] */
    char temp = a[j];
    a[j] = a[k];
    a[k] = temp;

    /* Reverse */
    int r = n;
    int s = j + 1;
    while(r > s) {
        temp = a[r];
        a[r] = a[s];
        a[s] = temp;
        --r;
        ++s;
    }

    return 1;
}

I have tested the code give above, but still if you can find any bugs, please reply back.

Advertisement