tag:blogger.com,1999:blog-34173777.post8751419824940679612..comments2020-09-24T20:13:07.803+05:30Comments on DeeKaying @ Pinterest: Permutations of a string containing duplicates (C++ Version)Divye Kapoorhttp://www.blogger.com/profile/05987327171759168375noreply@blogger.comBlogger13125tag:blogger.com,1999:blog-34173777.post-71305409057967642652011-06-22T22:17:08.995+05:302011-06-22T22:17:08.995+05:30Hi Divye,
Good post :)
Above all, the way you answ...Hi Divye,<br />Good post :)<br />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! :)Jagadishhttps://www.blogger.com/profile/07708952510930779716noreply@blogger.comtag:blogger.com,1999:blog-34173777.post-55865508244806693212011-06-12T13:06:52.650+05:302011-06-12T13:06:52.650+05:30I finally managed to find the time to code up the ...I finally managed to find the time to code up the solution to the distinct permutations problem.<br /><br />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. <br /><br />The solution is posted on my blog post at http://www.divye.in/2011/06/printing-all-permutations-of-string.htmlDivye Kapoorhttps://www.blogger.com/profile/05987327171759168375noreply@blogger.comtag:blogger.com,1999:blog-34173777.post-36054150062096897532011-04-14T14:30:04.639+05:302011-04-14T14:30:04.639+05:30Hey Pawan,
Glad you liked the post. I went through...Hey Pawan,<br />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.<br /><br />DivyeDivye Kapoorhttps://www.blogger.com/profile/05987327171759168375noreply@blogger.comtag:blogger.com,1999:blog-34173777.post-89366760484528100402011-04-13T11:02:27.985+05:302011-04-13T11:02:27.985+05:30@divye sir: Nice one.Superlike. :) :)
Well actua...@divye sir: Nice one.Superlike. :) :)<br /><br /> Well actually I had a notion that this particular problem can never be solved by iterative method. I am glad you proved me wrong.<br /><br />Even I wrote a code for the same and that being<br /><br />/*<br /> Name: Combos<br /> Copyright: <br /> Author: Pawan Seerwani.<br /> Date: 05/04/11 23:57 Description: This program prints all possible permutations of a words[with no repeated letters].<br />*/<br />#include<br />#include<br />using namespace std;<br />char* combos(char a[50],char b[50])<br />{<br /> if(strlen(b)==1)<br /> {<br /> cout<<a<<b<<endl;<br /> return a;<br /> }<br /> else<br /> {<br /> char c[50],e[50];<br /> int i,j;<br /> strcpy(c,a);<br /> strcpy(e,b);<br /> for(i=0;i<strlen(b);i++)<br /> {<br /> c[strlen(a)]=b[i];<br /> c[strlen(a)+1]=0;<br /> for(j=i;j<strlen(b)-1;j++)<br /> {<br /> e[j]=e[j+1];<br /> }<br /> e[j]=0;<br /> combos(c,e);<br /> strcpy(c,a);<br /> strcpy(e,b);<br /> <br /> }<br /> <br /> }<br />}<br />int main()<br />{<br /> char b[50]="pawan";<br /> char a[50]="";<br /> combos(a,b);<br /> system("pause");<br />}<br />//Till here<br /><br />But my code doesnt care for duplicate permutations. :( <br /><br /> P.S:Your sol is very cool and short. :)Anonymoushttps://www.blogger.com/profile/03166679966160204233noreply@blogger.comtag:blogger.com,1999:blog-34173777.post-38259147910587962372011-04-13T11:00:44.505+05:302011-04-13T11:00:44.505+05:30@divye sir: Nice one.Superlike. :) :)
Well actua...@divye sir: Nice one.Superlike. :) :)<br /><br /> Well actually I had a notion that this particular problem can never be solved by iterative method. I am glad you proved me wrong.<br /><br />Even I wrote a code for the same and that being<br /><br />/*<br /> Name: Combos<br /> Copyright: <br /> Author: Pawan Seerwani.<br /> Date: 05/04/11 23:57 Description: This program prints all possible permutations of a words[with no repeated letters].<br />*/<br />#include<br />#include<br />using namespace std;<br />char* combos(char a[50],char b[50])<br />{<br /> if(strlen(b)==1)<br /> {<br /> cout<<a<<b<<endl;<br /> return a;<br /> }<br /> else<br /> {<br /> char c[50],e[50];<br /> int i,j;<br /> strcpy(c,a);<br /> strcpy(e,b);<br /> for(i=0;i<strlen(b);i++)<br /> {<br /> c[strlen(a)]=b[i];<br /> c[strlen(a)+1]=0;<br /> for(j=i;j<strlen(b)-1;j++)<br /> {<br /> e[j]=e[j+1];<br /> }<br /> e[j]=0;<br /> combos(c,e);<br /> strcpy(c,a);<br /> strcpy(e,b);<br /> <br /> }<br /> <br /> }<br />}<br />int main()<br />{<br /> char b[50]="pawan";<br /> char a[50]="";<br /> combos(a,b);<br /> system("pause");<br />}<br />//Till here<br /><br />But my code doesnt care for duplicate permutations. :( <br /><br /> P.S:Your sol is very cool and short. :)Anonymoushttps://www.blogger.com/profile/03166679966160204233noreply@blogger.comtag:blogger.com,1999:blog-34173777.post-66852105143200744852009-05-07T09:59:00.000+05:302009-05-07T09:59:00.000+05:30http://www.japanfloristshop.com
Send gifts tojap...http://www.japanfloristshop.com<br /><br /><br />Send gifts tojapanfloristshop. Online delivery of flowers toJapanfloristshop , gift to japanfloristshop .chocolates, cakes, watches, teddy, sweets, fresh fruits, dry fruits.<br />Anniversary, birthday, wedding gifts, cakes tojapanfloristshop.liladashttps://www.blogger.com/profile/04824980047151835418noreply@blogger.comtag:blogger.com,1999:blog-34173777.post-13484472411705789322009-05-05T12:34:00.000+05:302009-05-05T12:34:00.000+05:30This comment has been removed by a blog administrator.Unknownhttps://www.blogger.com/profile/07393114438072953691noreply@blogger.comtag:blogger.com,1999:blog-34173777.post-56571550998632930162008-11-30T17:00:00.000+05:302008-11-30T17:00:00.000+05:30thats a really cool solutionthats a really cool solutionAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-34173777.post-76369818167110146712008-11-21T21:28:00.000+05:302008-11-21T21:28:00.000+05:30vickey: You shouldn't be using Turbo C++ anymo...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.<BR/><BR/>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.<BR/>Hope that helps. :-)Divye Kapoorhttps://www.blogger.com/profile/05987327171759168375noreply@blogger.comtag:blogger.com,1999:blog-34173777.post-14729618568020829882008-11-21T21:04:00.000+05:302008-11-21T21:04:00.000+05:30whether it will work for turbo c++and what modific...whether it will work for turbo c++<BR/>and what modification should we have to do for running it in c++Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-34173777.post-4722976802791393022008-10-14T00:29:00.000+05:302008-10-14T00:29:00.000+05:30Sort providing an O(n*log n) complexity is a non i...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.Divye Kapoorhttps://www.blogger.com/profile/05987327171759168375noreply@blogger.comtag:blogger.com,1999:blog-34173777.post-24667694801128958912008-10-13T20:01:00.000+05:302008-10-13T20:01:00.000+05:30Fast?! std::sort is O(n*log(n)) and std::next_perm...Fast?! std::sort is O(n*log(n)) and std::next_permutation is O(n). Gaah!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-34173777.post-63379774322740432802008-10-12T15:36:00.000+05:302008-10-12T15:36:00.000+05:30nice one - I was solving a similar problem in C# a...nice one - I was solving a similar problem in C# and came up with (http://blog.figmentengine.com/2008/10/permutations-and-anagrams.html)<BR/><BR/>however your C++ solution is a nice one to know about!fehttps://www.blogger.com/profile/10497505263673073471noreply@blogger.com