No. 36 - Permutation

Questions: Please print all permutations of a given string. For example, print “abc”, “acb”, “bac”, “bca”, “cab”, and “cba” when given the input string “abc”.

Analysis: For many candidates, it is not a simple problem to get all permutations of a set of characters. In order to solve such a problem, candidates might try to divide it into simple subproblems. An input string is partitioned into two parts. The first part only contains the first characters, and the second part contains others. As shown in Figure 1, a string is divided into two parts with different background colors.

Figure 1: The process to get permutations of a string. (a) A string is divided into two parts of which the
first part only contains the first character, and the second part contains others (with gray background). (b)
All characters in the second part are swapped with the first character one by one.

This solution gets permutations of a given string with two steps. The first step is to swap the first
character with the following characters one by one. The second step is to get permutations of the string excluding the first character. Take the sample string “abc” as an example. It gets permutations of “bc” when the first character is ‘a’. It then swaps the first character with ‘b’, gets permutations of “ac”, and finally gets permutation of “ba” after swapping the first character with ‘c’.

The process to get permutations of a string excluding the first character is similar to the process to
get permutations of a whole string. Therefore, it can be solved recursively, as shown below:

 

void Permutation(char* pStr)

{
    if(pStr == NULL)
        return;
    PermutationCore(pStr, pStr);
}

void PermutationCore(char* pStr, char* pBegin)

{
    char *pCh = NULL;
    char temp;
    if(*pBegin == '\0')
    {
        printf("%s\n", pStr);
    }
    else
    {
        for(pCh = pBegin; *pCh != '\0'; ++ pCh)
        {
            temp = *pCh;
            *pCh = *pBegin;
            *pBegin = temp;

            PermutationCore(pStr, pBegin + 1);

            temp = *pCh;
            *pCh = *pBegin;
            *pBegin = temp;
        }
    }
}

The discussion about this problem is included in my book <Coding Interviews: Questions, Analysis & Solutions>, with some revisions. You may find the details of this book on Amazon.com, or Apress.

The author Harry He owns all the rights of this post. If you are going to use part of or the whole of this ariticle in your blog or webpages, please add a reference to http://codercareer.blogspot.com/. If you are going to use it in your books, please contact him via zhedahht@gmail.com . Thanks.