# All possible combinations of a string

Discussion in 'C++' started by anjanesh, Dec 27, 2004.

1. ### anjaneshNew Member

Joined:
Dec 25, 2004
Messages:
16
0
Trophy Points:
0
Occupation:
Freelance Developer
Location:
Nerul, Navi Mumbai, India
http://anjanesh.com
All possible combinations of a string
1. Finds all possible cominations of a given string. The total number of combinations with recurrences is the factorial of the string length.
2. Have given the word 'post' as an example since if I included a cin >> word; then a user may unconscientiously enter a long word which will take toooo long to end. To change to another word change the string str.
3. A 9 letter word like 'aeroplane' can take around 40 seconds on a 1GHz machine. A 10 letter word will take 9 x 40 s - thats 6 mins! So watch out for the string length.
4. This may time according to the length of the string str

Code:
// Combination

#include<iostream.h>
#include<string.h>
#include<conio.h>

unsigned long fact(unsigned long); // finds factorial of a number
void swap(int[],int,int);
void display(int[],char[]);

void main()
{
// clrscr(); // Remove the first comment tag if running in TC++ or BC++ DOS mode
int j,k,n;

unsigned long i;
char str[]="post"; // small word
n=strlen(str);
int*key=new int[n+1];
key[0]=n; // key[0] contains the total no: of letters
for (i=1;i<=key[0];i++)
key[i]=i;
display(key,str);
swap(key,key[0],key[0]-1);
display(key,str);
for (i=3;i<=fact(key[0]);i+=2)
{
for (j=key[0]-1;j>=0;j--)
{
if ((i-1)%fact(j)==0)
{
for (k=1;k<=key[0]-j-1;k++)
if (key[k]==key[key[0]-j])
}
}
display(key,str);
swap(key,key[0],key[0]-1);
display(key,str);
}
cout << "\nTotal no: of combinations = " << key[0] << "! = " << i-1;
getch();
}

unsigned long fact(unsigned long f)
{
return f==0?1:f*fact(f-1);
}

void swap(int k[],int a,int b)
{
int t=k[a];k[a]=k[b];k[b]=t;
}

void display(int k[],char s[])
{
for(int i=1;i<=k[0];i++)
cout << s[k[i]-1];
cout << '\t';
}

{
k[i]++;
if (k[i]==k[0]+1)
k[i]=1;
}

Last edited: Dec 28, 2004

Joined:
Jul 12, 2004
Messages:
15,376
388
Trophy Points:
83
First of all welcome to the go4expert forums and yes a nice code also.

Can you mention which compiler it will compile as its not meant for Visual Studio as it has clrscr method.

Thanks
Shabbir Bhimani

3. ### anjaneshNew Member

Joined:
Dec 25, 2004
Messages:
16
0
Trophy Points:
0
Occupation:
Freelance Developer
Location:
Nerul, Navi Mumbai, India
http://anjanesh.com
I wrote this using TC++ 3.1.
It compiled and worked in TC++ 3.1 and Borland C++ 3.11.
Remove clrscr() and it compiles and executes in vc++6 - checked.

Joined:
Jul 12, 2004
Messages:
15,376
388
Trophy Points:
83
Thats nice.

5. ### sanjit_DeveloperNew Member

Joined:
Dec 27, 2004
Messages:
3
0
Trophy Points:
0
Hi,
Thats an extraordinary contribution frnd.Thanx.
sanjit khasnois

6. ### jcnovoaNew Member

Joined:
Oct 11, 2005
Messages:
1
0
Trophy Points:
0
Thank you... with a little modification, I was able to make it work for my C# app that I am working on. Great code... too bad google ranks it so low in its engine

Joined:
Jul 12, 2004
Messages:
15,376
388
Trophy Points:
83
Google is slowly loosing the share and the quality in Search domain. In sitepoint forum in some thread I read recently that within couple of years Google has lost from 90% of the share traffic to 48% and the rest have moved to Yahoo and MSN. Its probably because they are more interested in satisfying there Clients of adwords.

8. ### AlajNew Member

Joined:
Jul 20, 2006
Messages:
4
0
Trophy Points:
0
hello
this is realy a very good code ...

can any one tell me that what is the basic process of function

i need its processing flow plz if anybody can help me i'll be thankful

9. ### anjaneshNew Member

Joined:
Dec 25, 2004
Messages:
16
0
Trophy Points:
0
Occupation:
Freelance Developer
Location:
Nerul, Navi Mumbai, India
http://anjanesh.com
I should've documented this when I wrote this in college 4 yrs back.
I'll try to remember and repost this code with documentation.

10. ### AlajNew Member

Joined:
Jul 20, 2006
Messages:
4
0
Trophy Points:
0
hello
one more question is that plz tell me the logic of "if ((i-1)%fact(j)==0)" this condition in this code..
and plz send that documentation as soon as possible

11. ### anjaneshNew Member

Joined:
Dec 25, 2004
Messages:
16
0
Trophy Points:
0
Occupation:
Freelance Developer
Location:
Nerul, Navi Mumbai, India
http://anjanesh.com
I spent a lot of time try to get this algo in college days. But never bothered to write down the steps.
I'll defintely post the documentation here in a few weeks time after I recollect the steps.

Joined:
Jul 12, 2004
Messages:
15,376
388
Trophy Points:
83
I have documented the code completely
Code:

// Combination

#include<iostream.h>
#include<string.h>
#include<conio.h>

unsigned long fact(unsigned long); // finds factorial of a number
void swap(int[],int,int);
void display(int[],char[]);

/***********************************************************************/
/// <b>Function: main</b>
///
///	\param	NONE
///
/// \return	void
///
/// \remarks	main function
///
/***********************************************************************/
void main()
{
int j,k,n;
unsigned long i;

char str[]="G4EF"; // sample small word

n=strlen(str); // Get the length of the string

int*key=new int[n+1]; // Allocate buffer of size n+1

key[0]=n; // key[0] contains the total no: of letters

// Assign all the keys an index from the string
for (i=1;i<=key[0];i++)
key[i]=i;

display(key,str); // Displays the string

swap(key,key[0],key[0]-1); // swaps the key values n and n-1

display(key,str); // Displays the string

// store the factorial once and so it does not calulate each time
unsigned long num = fact(key[0]);

// Loop till factorial n so we get all the combination of strings
// It starts with i=3 as we already have 2 combination
// Its increments by 2 as we get 2 combination with the help of swap
for (i=3;i<=num;i+=2)
{
// Loop for all the elements of the string
for (j=key[0]-1;j>=0;j--)
{
// Edited by Shabbir
// Can be avoided
//if ((i-1)%fact(j)==0)
{
Add(key,key[0]-j);  // Increment the key in a cyclic form
for (k=1;k<=key[0]-j-1;k++)
{
// If kth index in key is euqal to n-jth index
if (key[k]==key[key[0]-j])
{
Add(key,key[0]-j); // Increment the key in a cyclic form
k=0;
}
}
}
}
display(key,str); // Displays the string
swap(key,key[0],key[0]-1); // swaps the key values
display(key,str); // Displays the string
}
cout << "\nTotal no: of combinations = " << key[0] << "! = " << i-1;
cout<<endl;
getch();
}

/***********************************************************************/
/// <b>Function: fact</b>
///
/// \param	long f	(in)
///
/// \return	unsigned long
///
/// \remarks	returns the factorial of parameter f using recursion
///
/***********************************************************************/
unsigned long fact(unsigned long f)
{
return f==0?1:f*fact(f-1);
}

/***********************************************************************/
/// <b>Function: swap</b>
///
/// \param	k[]	(out)
///
/// \param	a	(in)
///
/// \param	b	(in)
///
/// \return	void
///
/// \remarks	Swaps the index of the key.
///
/***********************************************************************/
void swap(int k[],int a,int b)
{
int t=k[a];k[a]=k[b];k[b]=t;
}

/***********************************************************************/
/// <b>Function: display</b>
///
/// \param	k[]	(in)
///
/// \param	s[]	(in)
///
/// \return	void
///
/// \remarks	Displays the string using the key
///
/***********************************************************************/
void display(int k[],char s[])
{
for(int i=1;i<=k[0];i++)
cout << s[k[i]-1];
cout << '\t';
}

/***********************************************************************/
///
/// \param	k[]	(out)
///
/// \param	i	(in)
///
/// \return	void
///
/// \remarks	Increments the key values of the index i. If it crosses
///				the max limit resets back to 1. i.e. in cyclic form.
///
/***********************************************************************/
{
k[i]++;
if (k[i]==k[0]+1)
k[i]=1;
}

Also I have removed some unnecessary calculations which now speeds up the process. I have added "Added/Edited by shabbir" so that its easily trackable.

13. ### anjaneshNew Member

Joined:
Dec 25, 2004
Messages:
16
0
Trophy Points:
0
Occupation:
Freelance Developer
Location:
Nerul, Navi Mumbai, India
http://anjanesh.com
Hats off to you shabbir ! I cant belive you figured this out so soon. You are a true algo expert !
Thanks

14. ### AlajNew Member

Joined:
Jul 20, 2006
Messages:
4
0
Trophy Points:
0
thanks alot dear

Joined:
Jul 12, 2004
Messages:
15,376
388
Trophy Points:
83
My pleasure.

16. ### BlasterBlangNew Member

Joined:
Nov 13, 2006
Messages:
10
0
Trophy Points:
0
thanks.....nice one.

Last edited by a moderator: Nov 14, 2006

Joined:
Jul 12, 2004
Messages:
15,376
388
Trophy Points:
83

18. ### BlasterBlangNew Member

Joined:
Nov 13, 2006
Messages:
10
0
Trophy Points:
0
ok fine

19. ### aisha.ansari84New Member

Joined:
Feb 13, 2008
Messages:
82
1
Trophy Points:
0
nice code

Joined:
Feb 13, 2008
Messages:
103