The following code can be used to generate permutations of the string.. but
still some bugs are there like to avoid already printed char etc.. however
logic will be similar..
order will be less that n^2
// stringPermutration.cpp : Defines the entry point for the console
application.
//
#include "stdafx.h"
#include<stdio.h>
#include<string.h>
#include<string>
#include<iostream>
using namespace std;
using namespace std;
void Permutate(int pos,char *prefix,char *str,char *src)
{
char *prefix1,*str1,*src1;
prefix1 = new char[20];
memset(prefix1,0,20);
str1 = new char[20];
memset(str1,0,20);
src1 = new char[20];
memset(src1,0,20);
if(pos >= strlen(src))
return;
if(strlen(str)!=0)
{
strcpy(prefix1,prefix);
strcpy(str1,str);
strcpy(src1,src);
prefix1[strlen(prefix1)]=str1[0];
prefix1[strlen(prefix1)+1]='\0';
for(int i=0;i<strlen(str1);i++)
{
str1[i]=str1[i+1];
}
}
else
{
int j;
int pos1=pos+1;
for(int i=pos1,j=0;j<strlen(src);)
{
str[j]=src[(i+j)%strlen(src)];
j++;
//i++;
}
strcpy(prefix1,"");
strcpy(str1,str);
pos++;
}
strcpy(prefix,prefix1);
strcpy(str,str1);
Permutate(pos,prefix,str,src);
for(int x=0;x<strlen(str1);x++)
{
printf("\n %s",prefix1);
printf("%c",str1[x]);
}
}
int _tmain(int argc, _TCHAR* argv[])
{
char *str = new char[20];
char *remaining = new char[20];
memset(str,0,20);
memset(remaining,0,20);
strcpy(str,"abcd");
strcpy(remaining,str);
char *prefix = new char[20];
memset(prefix,0,20);
Permutate(0,prefix,remaining,str);
return 0;
}
Thx,
--Gopi
On Thu, Jul 28, 2011 at 12:30 AM, Kamakshii Aggarwal
<[email protected]>wrote:
> in the above example y ac is not included in the substring?
>
>
> On Wed, Jul 27, 2011 at 3:45 PM, saurabh singh <[email protected]>wrote:
>
>> hmm o(nlogn) was for constructing the tree.Btw sorry for being unclear.
>> The best solution is the obvious one in this case.
>>
>>
>> On Wed, Jul 27, 2011 at 2:10 PM, surender sanke <[email protected]>wrote:
>>
>>> @ sunny , ur right!!
>>>
>>> surender
>>>
>>> On Wed, Jul 27, 2011 at 1:58 PM, sunny agrawal
>>> <[email protected]>wrote:
>>>
>>>> i don't find difference between your suffix tree approach and my simple
>>>> O(N^2) method
>>>> in both cases printf statement will be executed O(N^2) times
>>>> and in Suffix Tree approach will take some extra time of construction of
>>>> tree and extra space too !!!!!
>>>>
>>>> On Wed, Jul 27, 2011 at 1:45 PM, surender sanke <[email protected]>wrote:
>>>>
>>>>> *
>>>>> / \ \
>>>>> a b c
>>>>> / \
>>>>> b c
>>>>> /
>>>>> c
>>>>>
>>>>> prints *a*
>>>>> comes to b, appends a with b prints *ab*
>>>>> comes to c ,appends ab with c prints *abc*
>>>>> starts with new child
>>>>> prints *b*
>>>>> prints *bc*
>>>>> prints *c*
>>>>>
>>>>> surender
>>>>>
>>>>>
>>>>> On Wed, Jul 27, 2011 at 12:46 PM, sunny agrawal <
>>>>> [email protected]> wrote:
>>>>>
>>>>>> But still Printing O(N^2) substrings will take O(N^2) time isn't it ?
>>>>>>
>>>>>> On Wed, Jul 27, 2011 at 12:39 PM, surender sanke <[email protected]
>>>>>> > wrote:
>>>>>>
>>>>>>>
>>>>>>>
>>>>>>> @sunny
>>>>>>> consider *uncompressed* suffix tree, even with distinct elements
>>>>>>> maximum number of nodes with string length n formed will be 2n.
>>>>>>> once suffix tree is constructed, needs to traverse in dfs order
>>>>>>> appending the node found on the way.
>>>>>>> total complexity would be O(construction of suffix tree ) +
>>>>>>> O(traverse time).
>>>>>>>
>>>>>>> surender
>>>>>>>
>>>>>>>
>>>>>>> On Wed, Jul 27, 2011 at 12:00 PM, sunny agrawal <
>>>>>>> [email protected]> wrote:
>>>>>>>
>>>>>>>> @shiva viknesh
>>>>>>>> this is a different Question.......
>>>>>>>>
>>>>>>>> @saurabh
>>>>>>>> how is nlgn possible, total no of possible substrings are n^2
>>>>>>>>
>>>>>>>>
>>>>>>>> this is the O(n^2) solutionOn Wed, Jul 27, 2011 at 8:09 AM, saurabh
>>>>>>>> singh
>>>>>>>>
>>>>>>>> for(int l = 0; l < len; l++){
>>>>>>>> for(int i = 0; i < len-l; i++){
>>>>>>>> int j = i+l;
>>>>>>>> char temp = s[j+1];
>>>>>>>> s[j+1] = 0;
>>>>>>>> printf("%s\n", s+i);
>>>>>>>> s[j+1] = temp;
>>>>>>>> }
>>>>>>>> }
>>>>>>>>
>>>>>>>> <[email protected]> wrote:
>>>>>>>> >
>>>>>>>> > using suffix tree this can be done in o(nlogn) though will take
>>>>>>>> extra space.
>>>>>>>> >
>>>>>>>> > On Wed, Jul 27, 2011 at 12:47 AM, siva viknesh <
>>>>>>>> [email protected]> wrote:
>>>>>>>> >>
>>>>>>>> >> http://geeksforgeeks.org/?p=767
>>>>>>>> >>
>>>>>>>> >> On Jul 26, 11:49 pm, Pratz mary <[email protected]> wrote:
>>>>>>>> >> > how?
>>>>>>>> >> >
>>>>>>>> >> > On 26 July 2011 23:18, ankit sambyal <[email protected]>
>>>>>>>> wrote:
>>>>>>>> >> >
>>>>>>>> >> > > @vivin : Suffix trees are memory intensive..
>>>>>>>> >> >
>>>>>>>> >> > > This problem can be solved just by running 2 nested loops in
>>>>>>>> O(1)
>>>>>>>> >> > > space and O(n^2) time
>>>>>>>> >> >
>>>>>>>> >> > > --
>>>>>>>> >> > > 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.
>>>>>>>> >> >
>>>>>>>> >> > --
>>>>>>>> >> > regards Pratima :)
>>>>>>>> >>
>>>>>>>> >> --
>>>>>>>> >> 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.
>>>>>>>> >>
>>>>>>>> >
>>>>>>>> >
>>>>>>>> >
>>>>>>>> > --
>>>>>>>> > Saurabh Singh
>>>>>>>> > B.Tech (Computer Science)
>>>>>>>> > MNNIT ALLAHABAD
>>>>>>>> >
>>>>>>>> >
>>>>>>>> > --
>>>>>>>> > 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.
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>> --
>>>>>>>> Sunny Aggrawal
>>>>>>>> B-Tech IV year,CSI
>>>>>>>> Indian Institute Of Technology,Roorkee
>>>>>>>>
>>>>>>>> --
>>>>>>>> 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.
>>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>> --
>>>>>> Sunny Aggrawal
>>>>>> B-Tech IV year,CSI
>>>>>> Indian Institute Of Technology,Roorkee
>>>>>>
>>>>>> --
>>>>>> 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.
>>>>>
>>>>
>>>>
>>>>
>>>> --
>>>> Sunny Aggrawal
>>>> B-Tech IV year,CSI
>>>> Indian Institute Of Technology,Roorkee
>>>>
>>>> --
>>>> 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.
>>>
>>
>>
>>
>> --
>> Saurabh Singh
>> B.Tech (Computer Science)
>> MNNIT ALLAHABAD
>>
>>
>> --
>> 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.
>>
>
>
>
> --
> Regards,
> Kamakshi
> [email protected]
>
> --
> 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.
>
--
Thx,
--Gopi
--
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.
