8 replies to this topic

[noobsia]

I cant figure out how to do this.. can anyone tell me how to write this code ?
It helps me a lot if any stepsor any sample are given as my programming skill is very weak..T.T Thank you for any helps!

Write a recursive program that accepts an input n from the user and prints out all n! permutations of the n letters starting at a (assume that n is no greater than 26). A permutation of n elements is one of the n! possible orderings of the elements. As an example, when n = 3 you should get the following output.

sample output:

Enter number of letters: 3

bca cab cba acb bac abc


Thanks again! :D

[dargueta]

You need to use the permutation formula in addition to recursive functions. Read up on permutation mathematics on Wikipedia, do a few by hand, find a pattern, and then I'm sure you'll see how to do it in code. If not, don't hesitate to ask.

Permutation Mathematics

So if the formula is P(n,r)= n!/(n-r)! then you need to figure out a way to do the factorials. Hint: this is the recursive part...

Edited by dargueta, 22 June 2008 - 09:01 AM.

[WingedPanther]

Unfortunately, the permutation formula doesn't help him.

What you need to figure out is what the "first" permutation should look like (such as "abc"), how to move from that string to the "next" permutation (such as "acb"), and finally how to detect the "last" permutation (such as "cba").

Fair warning: entering 26 with a recursive formula is very likely to generate memory issues if you aren't careful.

[noobsia]

Hey , in my mindset ,i think of this ..but i dont know how to solve the errors...
In this code , for example, when user put 3 letter,with the factorial loop, it will cause the program to loop 6 times and in inner loop - create a letter one by one in each group with a,b,c right ? -(that's what i think about , but is it correct?)

The result would be like this;
abc abc abc abc abc abc

(I am wondering whether i correct or not ? Can anyone tell me ?)


But I get these error...
error C2059: syntax error : '[' ;
error C2109: subscript requires array or pointer type;

What's that =.=?

#include<stdio.h>

long factorial (long number);
int loop1,loop2,ans;
char a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,x,w,y,z;
char [25]={ a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,x,w,y,z};

int main(void)

{
	

	printf("Enter Letter : %ld\n",ans);
		
	for(loop1=0;loop1<factorial(ans);loop1++)
	{
		for(loop2=0;loop2<ans;loop2++)
		{
			printf("%c",a[loop2]);
		}
		printf("  ");
	}		
	return 0;
}


long factorial( long number )                          
{                                                       
			                                       
  if ( number <= 1 ) {                                 
    return 1;                                        
	}                                      
	else {                   
		  return ( number * factorial( number - 1 ) );        
		   }                                   
		                                                       
}       

If i am correct, can anyone tell me how to make it to
bca cab cba acb bac abc ??

Please..
TQ

Edited by WingedPanther, 24 June 2008 - 09:18 AM.
add code tags

[WingedPanther]

Factorials are not relevant to the code you are trying to make. There are two types of permutations: the actual sequences, and the number of sequences. dargueta gave you the formula for the number of sequences, but not how to produce the sequences, which is what you are trying to do.
I would print the permutations in lexical order: "abc", "acb", "bac", "bca", "cab", "cba" You will need to use a LOT of string functions to identify the next item in the order.

[dargueta]

Not really. If you start with a char array containing "abc" and just loop through it, incrementing each one using modular arithmetic, you'll eventually come up with everything. The permutation formula will just tell you how many times you need to loop.

[G_Morgan]

You'll need functions that can do the following:
1. Take a string and an array index and return an output string without the specified character.
2. Take a single character and an array of characters and produce an output array with the character spliced to the front of the input string.
3. Take an input character and an array of strings and product an output array of strings with the second step performed for each input member.

Then basically your permutation function is such that:
4. A string of length one returns an array of strings of size one with the input string being the only entry. (base case)
5. A string of length > 1 works by iterating across the string, removing the current character via 1 and then calingl permutation on it's result. Then splice the character to the front of the output. Naturally combine the output arrays for each character.

[dargueta]

I'm telling you, my way is easier...

char charArray[27]; //fill this with nulls

int numberOfPlaces = 0;


void main(void)

{

    printf("Number of places: ");

    scanf("%d",&numberOfPlaces);


    //fill arrays with appropriate starting values

    memset(charArray,0,27*sizeof(char));

    int i;

    for(i = 0; i < numberOfPlaces; ++i)

        charArray[i] = (char)((int)'A' + i);

    //this does all the permutation work

    permute(charArray,0, numberOfPlaces);

}


void permute(char *arr, int start, int numChars)

{

    if(start < numChars - 1)

        permute(arr, start + 1, numChars);

    else if (start >= numChars)

        return;


    for(int i = 0; i < numChars - start; ++i)

    {

        ++arr[start];

        printf("%s",arr);

        permute(arr,start + 1,numChars);

    }

}

Edited by dargueta, 26 June 2008 - 03:55 PM.
Fixed error

[G_Morgan]

Yes but I like generality so returning an array of strings, then printing the array out, is better :) .