How are You all?
I guess everyone’s mind is stressed now for a bloody long vacation.However I gotta post here
just to share one thrilling code with you.Infact I couldn’t but inform it all of you.Everyone knows
that we were given a assignment by Rasel Sir on typical Permutation algorithm such as to remove repetition
,to sort lexicographically etc.Might be some of us solved it,but with different algo for all specific task.
I also solved it but had used different algo for different task.I even surfed through net to find out such a code
,maybe for my inexperience how to search diligently,I failed to manage it.However I managed it myself few days
ago in this damn vacation(Im confused!!was it really damn vacation??:P)Though we know STL’s “next_permutation”
do this job perfectly,I find two flaw there.
1)It takes much time even than of mine!! 2)It’s a relative flaw of STL(Plz Recall that I said Relative)is that
somehow its odd to use STL without knowing How it works.
Well..I don’t want to stretch my introduction more..Here directly code goes:
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
bool vis[10000];
long N;
char p[10000],a[10000];
int cmp(const void *a,const void *b)
{
char *x=(char*)a;
char *y=(char*)b;
return *x-*y;
}
void check(long how)
{
long i;
if(how==N)
{
printf(“%s\n”,p);
return;
}
char pr=’-‘; //This for switching off the repetition
for(i=0;i<N;i++)
{
if(!vis[i]&&a[i]!=pr)
{
pr=a[i];
p[how]=a[i];
vis[i]=1;
check(how+1);
vis[i]=0;
}
}
}
int main()
{
while(gets(a))
{
N=strlen(a);
p[N]=”;
qsort(a,N,sizeof(char),cmp);
check(0);
}
return 0;
}
And short analysis on this code goes here:
Time complexity:
First of all,I wanna say my ability of analysing algo is poor even if it’s my own algo!!
As Far my ability,What I got is that Max depth of Recursion of above code is “Length of String”.
Let, Max depth=N and in each depth loop runs N time each making it a exponential algorithm
of like N^N.
For The string of length 11:”abcdefghijk” it takes almost 7.81 sec in Intel Dual core 2.20GHz Pc
whereas for same string STL takes 9.37 sec in same PC.(Time measured without printing results)
…Hope friends you might find it useful for ACM solving and you will notify me my errors and suggest
how to develop it..
Thanks
Sayem Mohammad Imtiaz
CUET CSE 08