#include <cstdio>
#include <cstring>
using namespace std;
const int MX = 1000;
char str[MX], sol[MX];
bool seen[MX] = {0};
void print(int n, int k=0) {
if(k==n) {
sol[n] = 0; printf("%s\n", sol);
return;
}
for(int i = 0; i < n; i++) {
if(!seen[i]) {
sol[k] = str[i];
seen[i] = 1; print(n, k+1); seen[i] = 0;
}
}
}
int main() {
scanf("%s", &str);
print(strlen(str));
}
On Jul 28, 12:03 am, "*$*" <gopi.komand...@gmail.com> wrote:
> 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
> <kamakshi...@gmail.com>wrote:
>
>
>
> > in the above example y ac is not included in the substring?
>
> > On Wed, Jul 27, 2011 at 3:45 PM, saurabh singh <saurab...@gmail.com>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 <surend...@gmail.com>wrote:
>
> >>> @ sunny , ur right!!
>
> >>> surender
>
> >>> On Wed, Jul 27, 2011 at 1:58 PM, sunny agrawal
> >>> <sunny816.i...@gmail.com>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
> >>>> <surend...@gmail.com>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 <
> >>>>> sunny816.i...@gmail.com> 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 <surend...@gmail.com
> >>>>>> > 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 <
> >>>>>>> sunny816.i...@gmail.com> 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;
> >>>>>>>> }
> >>>>>>>> }
>
> >>>>>>>> <saurab...@gmail.com> 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 <
> >>>>>>>> sivavikne...@gmail.com> wrote:
>
> >>>>>>>> >>http://geeksforgeeks.org/?p=767
>
> >>>>>>>> >> On Jul 26, 11:49 pm, Pratz mary <pratima.m...@gmail.com> wrote:
> >>>>>>>> >> > how?
>
> >>>>>>>> >> > On 26 July 2011 23:18, ankit sambyal <ankitsamb...@gmail.com>
> >>>>>>>> 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
> >>>>>>>> algogeeks@googlegroups.com.
> >>>>>>>> >> > > To unsubscribe from this group, send email to
> >>>>>>>> >> > > algogeeks+unsubscr...@googlegroups.com.
> >>>>>>>> >> > > 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 algogeeks@googlegroups.com.
> >>>>>>>> >> To unsubscribe from this group, send email to
> >>>>>>>> algogeeks+unsubscr...@googlegroups.com.
> >>>>>>>> >> 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 algogeeks@googlegroups.com.
> >>>>>>>> > To unsubscribe from this group, send email to
> >>>>>>>> algogeeks+unsubscr...@googlegroups.com.
> >>>>>>>> > 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 algogeeks@googlegroups.com.
> >>>>>>>> To unsubscribe from this group, send email to
> >>>>>>>> algogeeks+unsubscr...@googlegroups.com.
> >>>>>>>> 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 algogeeks@googlegroups.com.
> >>>>>>> To unsubscribe from this group, send email to
> >>>>>>> algogeeks+unsubscr...@googlegroups.com.
> >>>>>>> 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 algogeeks@googlegroups.com.
> >>>>>> To unsubscribe from this group, send email to
> >>>>>> algogeeks+unsubscr...@googlegroups.com.
> >>>>>> 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 algogeeks@googlegroups.com.
> >>>>> To unsubscribe from this group, send email to
> >>>>> algogeeks+unsubscr...@googlegroups.com.
> >>>>> 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 algogeeks@googlegroups.com.
> >>>> To unsubscribe from this group, send email to
> >>>> algogeeks+unsubscr...@googlegroups.com.
> >>>> 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 algogeeks@googlegroups.com.
> >>> To unsubscribe from this group, send email to
> >>> algogeeks+unsubscr...@googlegroups.com.
> >>> 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 algogeeks@googlegroups.com.
> >> To...
>
> read more »
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
