Friday, October 10, 2008

Permutations of a string containing duplicates (C++ Version)

Update: This is part 1 of a 2 part series of posts that discuss generating all possible permutations/anagrams of a given string. This post discusses how to use the next_permutation function provided by the standard C++ library to generate the anagrams iteratively. The next post discusses a custom recursive implementation of how to achieve the same thing. See: Recursively printing all permutations of a string containing duplicate characters.

Have you ever thought of how to generate and display/print all possible permutations of a string (containing duplicate characters) such that every legal permutation appears atmost once in the final output, without taking a humungous amount of memory to keep track of all the permutations you have generated? This particular function utilizes a cool STL algorithm and generates all possible permutations of a string only once (whether the original string contained duplicates or not).

int dup_permute(char *str, size_t length) {
    int count = 0;
    std::sort(str, str+length);
    do {
        ++count;
        cout <<  str << '\n';
    }
    while(std::next_permutation(str, str+length));
    return count;
}


Of course, since the major work of this function is being done in the C++ standard library, an explanation of the standard library functions is in order.
First up is the std::sort function. Located in the <algorithm> header, true to its name, it sorts the given range of elements (in this case the string, specified by pointers to its first and last elements). std::next_permutation is a tough one to deal with. The working of this function is too convoluted to explain in a couple of sentences, so, I would recommend you look up this reference and this MSDN article. In short, next_permutation generates the next lexicographically ordered permutation of the given elements using no more than a constant amount of extra space. All that work is done using comparison, swapping and reversing a subset of elements in the array itself. Also, since there is no copying involved, this function is blazing fast. So, the next time someone asks for all permutations of a string, forget about recursion and look at this iterative version. Not only is it correct for the distinct elements case, it works even when the string does contain duplicates. If you liked it, don't forget to leave a comment.

13 comments:

  1. nice one - I was solving a similar problem in C# and came up with (http://blog.figmentengine.com/2008/10/permutations-and-anagrams.html)

    however your C++ solution is a nice one to know about!

    ReplyDelete
  2. Anonymous8:01 PM

    Fast?! std::sort is O(n*log(n)) and std::next_permutation is O(n). Gaah!

    ReplyDelete
  3. Sort providing an O(n*log n) complexity is a non issue as the overall complexity is O(n*n!) in this implementation and the sorting is done only once in the entry of the function. Also, n is not likely to be much greater than 10-20 is it? Of course, I never claimed that this was the fastest way to do it. I only claim that it is one of the *correct* ways to handle cases where duplicates were present in the input string.

    ReplyDelete
  4. vickey9:04 PM

    whether it will work for turbo c++
    and what modification should we have to do for running it in c++

    ReplyDelete
  5. vickey: You shouldn't be using Turbo C++ anymore - it is a 16 bit compiler and it got obsolete sometime in 1991. C++ has gone a long way since then. In 1998, C++ was standardized by an ISO committee who also added many new features to the language - the major ones being templates and the Standard Template Library. Google "C++ templates tutorials" and "C++ STL" to learn more. I would sincerely suggest that you look at newer and better compilers/IDEs like the free Visual Studio Express 2008 edition available from Microsoft's site or Dev-C++ (http://www.bloodshed.net) on Windows and of course the gcc family on GNU/Linux and its variants.

    However, to get the above piece of code working on Turbo, you will have to replace the line std::sort(...) with an equivalent call to qsort(...) and create your own next_permutation(...) function; copy the original code from http://www.marknelson.us/2002/03/01/next-permutation , remove the template<...> line, replace all BidirectionalIterator with char * and you should be fine.
    Hope that helps. :-)

    ReplyDelete
  6. Anonymous5:00 PM

    thats a really cool solution

    ReplyDelete
  7. This comment has been removed by a blog administrator.

    ReplyDelete
  8. http://www.japanfloristshop.com


    Send gifts tojapanfloristshop. Online delivery of flowers toJapanfloristshop , gift to japanfloristshop .chocolates, cakes, watches, teddy, sweets, fresh fruits, dry fruits.
    Anniversary, birthday, wedding gifts, cakes tojapanfloristshop.

    ReplyDelete
  9. @divye sir: Nice one.Superlike. :) :)

    Well actually I had a notion that this particular problem can never be solved by iterative method. I am glad you proved me wrong.

    Even I wrote a code for the same and that being

    /*
    Name: Combos
    Copyright:
    Author: Pawan Seerwani.
    Date: 05/04/11 23:57 Description: This program prints all possible permutations of a words[with no repeated letters].
    */
    #include
    #include
    using namespace std;
    char* combos(char a[50],char b[50])
    {
    if(strlen(b)==1)
    {
    cout<<a<<b<<endl;
    return a;
    }
    else
    {
    char c[50],e[50];
    int i,j;
    strcpy(c,a);
    strcpy(e,b);
    for(i=0;i<strlen(b);i++)
    {
    c[strlen(a)]=b[i];
    c[strlen(a)+1]=0;
    for(j=i;j<strlen(b)-1;j++)
    {
    e[j]=e[j+1];
    }
    e[j]=0;
    combos(c,e);
    strcpy(c,a);
    strcpy(e,b);

    }

    }
    }
    int main()
    {
    char b[50]="pawan";
    char a[50]="";
    combos(a,b);
    system("pause");
    }
    //Till here

    But my code doesnt care for duplicate permutations. :(

    P.S:Your sol is very cool and short. :)

    ReplyDelete
  10. @divye sir: Nice one.Superlike. :) :)

    Well actually I had a notion that this particular problem can never be solved by iterative method. I am glad you proved me wrong.

    Even I wrote a code for the same and that being

    /*
    Name: Combos
    Copyright:
    Author: Pawan Seerwani.
    Date: 05/04/11 23:57 Description: This program prints all possible permutations of a words[with no repeated letters].
    */
    #include
    #include
    using namespace std;
    char* combos(char a[50],char b[50])
    {
    if(strlen(b)==1)
    {
    cout<<a<<b<<endl;
    return a;
    }
    else
    {
    char c[50],e[50];
    int i,j;
    strcpy(c,a);
    strcpy(e,b);
    for(i=0;i<strlen(b);i++)
    {
    c[strlen(a)]=b[i];
    c[strlen(a)+1]=0;
    for(j=i;j<strlen(b)-1;j++)
    {
    e[j]=e[j+1];
    }
    e[j]=0;
    combos(c,e);
    strcpy(c,a);
    strcpy(e,b);

    }

    }
    }
    int main()
    {
    char b[50]="pawan";
    char a[50]="";
    combos(a,b);
    system("pause");
    }
    //Till here

    But my code doesnt care for duplicate permutations. :(

    P.S:Your sol is very cool and short. :)

    ReplyDelete
  11. Hey Pawan,
    Glad you liked the post. I went through your solution and I'd like to let you know that a much smaller recursive solution exists which doesn't require 2 arrays. Give it some thought. If you're bot able to come up with a solution, comment here and I'll post the recursive solution that is also able to handle duplicates.

    Divye

    ReplyDelete
  12. I finally managed to find the time to code up the solution to the distinct permutations problem.

    It's probably the fastest you can get on this problem. It requires only a single array and generates all anagrams in worst case O(n*n!) time even in the presence of duplicates.

    The solution is posted on my blog post at http://www.divye.in/2011/06/printing-all-permutations-of-string.html

    ReplyDelete
  13. Hi Divye,
    Good post :)
    Above all, the way you answer and reply to comments with humility is awesome. (as in the comment that referred how to use it in turbo cpp which would have annoyed any geek). Keep up the good work! :)

    ReplyDelete