Hi Nishanth Pandey,
I got it. If str[end] char is present in
any index between [start, end) we would have already generated
permutations with str[end] character in index start. So no need to
generate those permutations again.
Again, Thank you very much for your programn :).
-Thanks,
Bujji
On Thu, Jan 9, 2014 at 3:56 AM, bujji jajala <[email protected]> wrote:
> 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].
