Hi Nishanth Pandey,
Excellent solution! It meets all
requirements in problem!
One thing I am finding hard to understand is your duplicate functions logic.
code is simple. But reason behind it I am finding hard.
I would write it like
bool duplicate(char str[], int start, int end)
{ if(start == end)
return false;
// Without loop
if (str[start] == str[end]) /* I would end up generating same
permutations for example abcacd here swapping a and a would repeat
same permutations. unfortunately this logic is not working well */
return true;
return false;
}
Why are you skipping if you find element you want to swap in between start
and end indexes in duplicate function?
Please let me know you intuition.
-Thanks,
Bujji
On Tue, Jan 7, 2014 at 6:08 AM, Nishant Pandey <[email protected]
> wrote:
> This will help u i guess :
>
> #include <iostream>
> #include <string.h>
> using namespace std;
>
> void swap(char str[],int m,int n ) {
> char temp=str[m];
> str[m]=str[n];
> str[n]=temp;
> }
> bool duplicate(char str[], int start, int end)
> { if(start == end)
> return false;
> else
> for(; start<end; start++)
> if (str[start] == str[end])
> return true;
> return false;
> }
> void Permute(char str[], int start, int end)
> {
> if(start >= end){
> cout<<str<<endl;
> return;
> }
> for(int i=start;i<=end;i++)
> { if(!duplicate(str,start,i))
> {
> swap(str,start,i);
> Permute(str,start+1,end);
> swap(str,start,i);
> }
> }
> }
>
> int main()
> {
> char Str[]="aba";
> Permute(Str,0,strlen(Str)-1);
> return 0;
> }
>
>
>
> NIshant Pandey
> Cell : 9911258345
> Voice Mail : +91 124 451 2130
>
>
>
>
> On Tue, Jan 7, 2014 at 4:44 PM, kumar raja <[email protected]>wrote:
>
>> This u can do it using the backtracking method. To know how to use
>> backtracking refer algorithm design manual by steve skiena.
>>
>>
>> On 7 January 2014 03:35, bujji jajala <[email protected]> wrote:
>>
>>> generate all possible DISTINCT permutations of a given string with some
>>> possible repeated characters. Use as minimal memory as possible.
>>>
>>> if given string contains n characters in total with m < n distinct
>>> characters each occuring n_1, n_2, ....n_m times where n_1 + n_2 + ...+ n_m
>>> = n
>>>
>>> program should generate n! / ( n_1! * n_2! * ....* n_m! ) strings.
>>>
>>> Ex:
>>> aba is given string
>>>
>>> Output:
>>>
>>> aab
>>> aba
>>> baa
>>>
>>>
>>> -Thanks,
>>> Bujji
>>>
>>> --
>>> You received this message because you are subscribed to the Google
>>> Groups "Algorithm Geeks" group.
>>> To unsubscribe from this group and stop receiving emails from it, send
>>> an email to [email protected].
>>>
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To unsubscribe from this group and stop receiving emails from it, send an
>> email to [email protected].
>>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to [email protected].
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
