Interview Questions - The Building 7

Print all permutations of a string

Write a function that would print permutations of all charaters in the string.

Algorithm Concept

This problem can be solved via recursively solving "subproblems".
We can notice that permutation of an array can be generated by taking exchanging first letter in an array with each other element, and then generating all permutations of sub array.

Solution

void permuteString(char *arr)
{
    permute(arr, 0, strlen(arr));
}

void permute(char *arr, int x, int size)
{
    if (x == size - 1)
    {
        printf("%s\n", arr);
    }

    for (int i = x; i < size; ++i)
    {
        xchg(arr, x, i);
        permute(arr, x + 1, size);
        xchg(arr, x, i);
    }
}