Problem in C

A

arka

Disciple
Consider a word "MACBETH"......and the no of permutations can be done with the 7 letters of MACBETH is 7! or 5040......My objective to write a program which will print all the permutations of MACBETH......The code should be a generalised one and can be valid for any problems or words like "Statistics"---where 3 's' ,2 't' and 2 'i' already present..........

Please give me a hint to solve it:)
 
sure this can be done. i mean u want to print out all combinations ?? I will just try it out and tell u. Meanwhile u can start with 3 letter word and then go for 4 letter word etc. i will use this approach. will let u know.
 
super_saiyan said:
eer...give me a example....i'll too try it ;)

give me the possibilities of
1)"CON"
2)"WORD"
3)"WORLD"
Click to expand...

See its like this...
if the alphabets are non repeating then its alphabets factorial like
CON - 3! ways i.e. 6 - CON, NOC, OCN, CNO, NCO, ONC
WORD - 4! ways i.e. 24 etc.

But in case of repeating alphabets like HELLO there will be 5! / 2!

And in case of HELLOO it will be 6! / (2! * 2! )

Hope i understood it right @arka
 
ya ofcourse it will be of same length.

the problem is generating all the combinations and not generating the ones already printed out.
 
I can think of a way but its complexity is O(n^n) in the worst case. Much too bad to be the correct solution. Give me some time...
 
I think the total number of combinations would be n!/x, where n is no. of letters in the word, and x is no of duplicate letters. If multiple letters are repeating, it would be n! / ( x*y*z*........)

e.g. For mississippi, it would be 11!/( 4*4*2).

Edit:

Heres the crudest idea I could think of.

1. The word is entered and collected in an array

2. Lenght is calculated.

3. Start a for i=n loop, where n is the lenght.

4. Now write a recursive function, which will go deeper into the word, till only 2 letters are left. Then jumble those two letters, and put the two results in a new array. At each level into the recursive loop, use a for loop with reducing number of turns. Also, before each word is put in the array, check it against the others, to see that its not getting repeated.

5. Finally, check the total number of words with the formula above, to see if theres any mistake.
 
^^ Yup u are right about this being one of the methods. Recursion can be used. But first you will need to sort out the word to take out common alphabets. Otherwise there could be repeatition problem.
 
But multiple arrays are no good here. The kind of memory you will need will go out of hand. Plus the number of comparisons (comparing against each previous word) is O((n!)!). (That is right - a double factorial!!!).
 
Rcursion can be used......but considering array.......it ll take a large no of array..................no of array will be different in different case....i.e. It ll vary with no of letters in the given word
 
tolal permutations are in form of x!/(y!*z!).........where x=no of total letters.....and y,z=no of repeated letters in the word
 
Instead of comparing to check that there are no repitions (which will require large memory and waste lot of time) you can maintain a list (2D array?) of all characters, as well as the number of their occurence in the original string.

The function would

1. Add a character from the list to a temporary string
2. Decrement its occurance number
3. Recursively call itself to work on the rest of the temp string.
4. Increment its occurance number
5. Repeat this for each character in the list

This way you are sure of eliminating repetition.

EDIT - Oh btw, the total number of combinations in, say, HELLLO is indeed 6!/3!, as for every arrangement of letters, you can permute the 3 L's among themselves in 3! ways, and hence 6! is 3! times the total number of unique combinations ;)
 
zhopudey said:
are you sure it'll be y!*z! ? I think it'll be y*z.
Click to expand...
It will be y! * z! coz "LLL" can be arranged in 3! ways.

I am working on the program but since i dont get time i could do it for up to 3 words. Still some tuning required in the recursion. Will try as soon as i get time.
And why consider memory now ?? Once u get the logic right i dont think memory will be a problem.
 
ujjawl your algo seems to be work for 1st letter of the word.....for second letter recursive calling may not work.......coz it ll jumble the letters from 3rd letter
 
It works here for me ... make sure that each child function does not have access to the "already filled" part of the string, and that the list of available characters is changed before calling it.

EDIT - this is the function I use -

Code: 
void permute(char buf[MAX][2],int n,char *store)
{
	int i,t=0;
	for(i=0;i<n;i++)
	{
		if(buf[i][1])
		{
			buf[i][1]--;		
			*store=buf[i][0];
			permute(buf,n,(store+1));
			buf[i][1]++;
			t=1;
		}
	}
	if(!t)
	{
		c++; //Increase word count
		print_str(store-1);
	}
}
 
The simplest approach for permutation...Recursion.

I have written the complete standard C program for you... :)

Code: 
#include <iostream.h>
#include <string.h>

void CharPermutation( char cStr[], char cAppend[] )
{
    int nLength = strlen(  cStr  );

    if ( nLength )
    {
        for( int i = 0; i < nLength; ++i )
        {
            char* cPerStr = new char[ nLength+1 ];

            int cnt;
            int cnt2;
            for( cnt = 0, cnt2 = 0; cnt < nLength; ++cnt, ++cnt2 )
            {
                if( cnt == i )
                {
                    cPerStr[ cnt ] = cStr[ ++cnt2 ];
                    continue; 
                }
                else
                    cPerStr[ cnt ] = cStr[ cnt2 ];
            }  

            cPerStr[ cnt ] = '\0';
          
            int nLen = strlen( cAppend );
            char* cPerAppend = new char [ nLen+2 ];
            strncpy( cPerAppend, cAppend, nLen );

            cPerAppend[ nLen ] = cStr[ i ];
            cPerAppend[ nLen+1 ] = '\0';

            CharPermutation( cPerStr, cPerAppend );

            delete [] cPerStr;
            delete [] cPerAppend;
        } 
    }
    else
    {
        cout << cAppend << endl; 
    }  
}

int main()
{
    char cStr[] = "Example";
    char cAppend[] = "\0";  

    CharPermutation( cStr, cAppend );

    cout << "Complete!" << endl;

    return 0;
}

Enjoy. :)
 
Back
Top