>> i more thing ... the code repeats same palindromes as in incase of ABA baa >> is coming twice.. Put back mk array in place and baa won't be repeated.
The idea is that out of all available options for filling a particular position in our partial solution at each round of backtracking we choose for each group of repeated characters, only one of them. In this way, we get only distinct permutations as output. On Jul 29, 3:37 pm, snehi jain <[email protected]> wrote: > i did a dry run on this code and didnt find the significance of mk array ... > so i did remove it from the code .. > and the code works fine .. > i more thing ... the code repeats same palindromes as in incase of ABA baa > is coming twice.. > > correct me if i am wrong ... > > On Fri, Jul 29, 2011 at 10:47 AM, Arun Vishwanathan > <[email protected]>wrote: > > > > > @amit:i am not clear about the code.Maybe could you take your example > > string aabc and explain a few steps that happen from your code??.The array > > mk is locally created for each function call and so I do not get how it > > keeps track of elements tried cos each time it is a new array. > > > On Fri, Jul 29, 2011 at 3:54 AM, amit karmakar > > <[email protected]>wrote: > > >> What my recursive solution does is that, > >> For all elements that can be used at position *k*, fix that element at > >> position *k* and then permute the rest of the elements. > >> So if are two same elements which can be used at position *k* we must > >> choose only one of it to avoid repeated permutations. > > >> Array mk[256] keeps a track of the elements that have already been > >> tried. > > >> >> Does there exist any better solution also, or this backtracking > >> solution is the best? > >> You should have a look at this: > > >>http://en.wikipedia.org/wiki/Permutation#Algorithms_to_generate_permu... > > >> On Jul 29, 12:34 am, Nitish Garg <[email protected]> wrote: > >> > Can you please explain what is the use of the array mk[256], how this > >> array > >> > solves the problem of repeated characters. > >> > Does there exist any better solution also, or this backtracking solution > >> is > >> > the best? > > >> -- > >> You received this message because you are subscribed to the Google Groups > >> "Algorithm Geeks" group. > >> To post to this group, send email to [email protected]. > >> To unsubscribe from this group, send email to > >> [email protected]. > >> For more options, visit this group at > >>http://groups.google.com/group/algogeeks?hl=en. > > > -- > > You received this message because you are subscribed to the Google Groups > > "Algorithm Geeks" group. > > To post to this group, send email to [email protected]. > > To unsubscribe from this group, send email to > > [email protected]. > > For more options, visit this group at > >http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
