Interview

String Permutation

Print all permutation of a given string.

Solution:

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.

NewPermutation

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

void PermutationCore(char* pStr, char* pBegin);
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;
 }
 }
}

int main(void)
{
 char string[64];
 sprintf(string, "%s", "abc");
 Permutation(string);
 return 0;
}
Advertisements