Sunday, February 3, 2013

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.

4 comments:

  1. Merhaba,


    Three cheers to you ! Hooray!!! I feel like I hit the jackpot on Permutation


    This thread is intended to serve as a place for the AWS community to report the quality of service we receive (or don't) for cases submitted under paid AWS support plans. Hopefully, this will help us determine if Amazon is delivering on their promises, regarding their support plans. To keep this thread readable, please keep replies concise, professional, and limited strictly to relevant facts. AWS Tutorial





    But nice Article Mate! Great Information! Keep up the good work!


    Ciao,
    Ajeeth

    ReplyDelete
  2. Hi Buddie,


    What you’re saying is absolutely correct No. 36 - Permutation, but this isn’t the exact situation everywhere. Where most smart folk work on a project - why can’t you do this the Boss asks :).


    I have posted a few times a issue about a couple of resources in my account which can not be deleted through AWS Management Console. No answer up to now. AWS Tutorial





    Thank you very much and will look for more postings from you.


    Obrigado,
    Ajeeth

    ReplyDelete
  3. Hallo,


    11/10!! Your blog is such a complete read. I like your approach with No. 36 - Permutation. Clearly, you wrote it to make learning a cake walk for me.


    I signed up my client for AWS last week. We did all the authorizations, credit card info, profile details, and even sent a support asking for the cap on email sends with SES to be increased. After 5 days we still are stuck with the "Your service sign-up is almost complete!" message and can't add services to the account. I have posted support requests and they are still sitting as unsigned. It is ironic that the support request to up the SES send limit was completed but no one will look at the basic account completion. How do we get this finalized so we can actually use the account? AWS Training





    Very useful article, if I run into challenges along the way, I will share them here.


    Shukran,
    Ajeeth

    ReplyDelete
  4. Bonjour,


    I genuinely do look forward for the time where you post some new write ups. Your blog make me feel so educated! Continue soaring and writing please.

    is this the right place for this kind of request? i would like to know when we can expect CodeCommit to be available in Frankfurt region,
    AWS Training also in general i would like to know if there is some place where i can see which service is planned to be deployed in which region etc. so we will know which service can we expect when and where.





    Anyways great write up, your efforts are much appreciated.


    Many Thanks,

    Irene Hynes

    ReplyDelete