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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s