All possible combinations of a string

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

  1. anjanesh

    anjanesh New Member

    Joined:
    Dec 25, 2004
    Messages:
    16
    Likes Received:
    0
    Trophy Points:
    0
    Occupation:
    Freelance Developer
    Location:
    Nerul, Navi Mumbai, India
    Home Page:
    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 Add(int[],int);
    
    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)
    			{
                    Add(key,key[0]-j);
                    for (k=1;k<=key[0]-j-1;k++)
    					if (key[k]==key[key[0]-j])
                        {Add(key,key[0]-j);k=0;}
    			}
    		}
    		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';
    }
    
    void Add(int k[],int i)
    {
    	k[i]++;
    	if (k[i]==k[0]+1)
    		k[i]=1;
    }
    
     
    Last edited: Dec 28, 2004
  2. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,375
    Likes Received:
    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. anjanesh

    anjanesh New Member

    Joined:
    Dec 25, 2004
    Messages:
    16
    Likes Received:
    0
    Trophy Points:
    0
    Occupation:
    Freelance Developer
    Location:
    Nerul, Navi Mumbai, India
    Home Page:
    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.
     
  4. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,375
    Likes Received:
    388
    Trophy Points:
    83
    Thats nice.
     
  5. sanjit_Developer

    sanjit_Developer New Member

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

    jcnovoa New Member

    Joined:
    Oct 11, 2005
    Messages:
    1
    Likes Received:
    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
     
  7. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,375
    Likes Received:
    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. Alaj

    Alaj New Member

    Joined:
    Jul 20, 2006
    Messages:
    4
    Likes Received:
    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

    void add (int[] , int);

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

    anjanesh New Member

    Joined:
    Dec 25, 2004
    Messages:
    16
    Likes Received:
    0
    Trophy Points:
    0
    Occupation:
    Freelance Developer
    Location:
    Nerul, Navi Mumbai, India
    Home Page:
    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. Alaj

    Alaj New Member

    Joined:
    Jul 20, 2006
    Messages:
    4
    Likes Received:
    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. anjanesh

    anjanesh New Member

    Joined:
    Dec 25, 2004
    Messages:
    16
    Likes Received:
    0
    Trophy Points:
    0
    Occupation:
    Freelance Developer
    Location:
    Nerul, Navi Mumbai, India
    Home Page:
    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.
     
  12. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,375
    Likes Received:
    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[]);
    void Add(int[],int);
    
    
    /***********************************************************************/
    /// <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
        
    	// Added by Shabbir
    	// 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';
    }
    
    
    /***********************************************************************/
    /// <b>Function: Add</b>
    ///
    /// \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.
    ///
    /***********************************************************************/
    void Add(int k[],int i)
    {
        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. anjanesh

    anjanesh New Member

    Joined:
    Dec 25, 2004
    Messages:
    16
    Likes Received:
    0
    Trophy Points:
    0
    Occupation:
    Freelance Developer
    Location:
    Nerul, Navi Mumbai, India
    Home Page:
    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. Alaj

    Alaj New Member

    Joined:
    Jul 20, 2006
    Messages:
    4
    Likes Received:
    0
    Trophy Points:
    0
    thanks alot dear
     
  15. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,375
    Likes Received:
    388
    Trophy Points:
    83
    My pleasure.
     
  16. BlasterBlang

    BlasterBlang New Member

    Joined:
    Nov 13, 2006
    Messages:
    10
    Likes Received:
    0
    Trophy Points:
    0
    thanks.....nice one.
     
    Last edited by a moderator: Nov 14, 2006
  17. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,375
    Likes Received:
    388
    Trophy Points:
    83
    BlasterBlang, Please confine links to signature only.
     
  18. BlasterBlang

    BlasterBlang New Member

    Joined:
    Nov 13, 2006
    Messages:
    10
    Likes Received:
    0
    Trophy Points:
    0
  19. aisha.ansari84

    aisha.ansari84 New Member

    Joined:
    Feb 13, 2008
    Messages:
    82
    Likes Received:
    1
    Trophy Points:
    0
  20. rahul.mca2001

    rahul.mca2001 New Member

    Joined:
    Feb 13, 2008
    Messages:
    103
    Likes Received:
    0
    Trophy Points:
    0
    there is no speed problem in the code now
     

Share This Page

  1. This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
    By continuing to use this site, you are consenting to our use of cookies.
    Dismiss Notice