to print permutations...

Discussion in 'C Programming' started by Shraddha, May 26, 2007.

Suppose we are having 3 variables...a,b,c
And we want to print the permutations of these variables...Such
as...abc,acb,bca...all 6 of them...
But we are not supposed to do it mannually...

I want to know that formula by which this can be possible...

Then that program will be ok for nnumber of variables....
Can anyone help me for that?

2. osmiumGuest

> Suppose we are having 3 variables...a,b,c
> And we want to print the permutations of these variables...Such
> as...abc,acb,bca...all 6 of them...
> But we are not supposed to do it mannually...
>
> I want to know that formula by which this can be possible...
>
> Then that program will be ok for nnumber of variables....
> Can anyone help me for that?

This might help

http://en.wikipedia.org/wiki/Permutations#Permutations_in_computing

It seems to have some "Pascalish" looking source code.

Because of the difficulties of handling templates, I would expect the source
code used by next_permutation ( or whatever) is in the \include\ directory
of your compiler. I never actually looked, though.

osmium, May 26, 2007

3. kingfoxGuest

On 5 26 , 9 13 , Shraddha <> wrote:
> Suppose we are having 3 variables...a,b,c
> And we want to print the permutations of these variables...Such
> as...abc,acb,bca...all 6 of them...
> But we are not supposed to do it mannually...
>
> I want to know that formula by which this can be possible...
>
> Then that program will be ok for nnumber of variables....
> Can anyone help me for that?

I think it's a algorithm problem. You should study the combination
mathematics. There is the algorithm for generating permutations in
this course.

kingfox, May 26, 2007
4. Eric SosmanGuest

> Suppose we are having 3 variables...a,b,c
> And we want to print the permutations of these variables...Such
> as...abc,acb,bca...all 6 of them...
> But we are not supposed to do it mannually...
>
> I want to know that formula by which this can be possible...
>
> Then that program will be ok for nnumber of variables....
> Can anyone help me for that?

Imagine that you had a function that would print
all the permutations of an array of N variables. Can
you think of a way to use that function to print all
the permutations of an array of N+1 variables?

Second question: Suppose N is equal to one. Can
you think of a way to print all the permutations of
a one-element array? If so, then by using the recipe
from the first paragraph you can find a method that
prints all the permutations of a two-element array.
Applying the recipe to that method gives you a way to
handle three-element arrays, then four, then five, ...

A convenient way to express this in C is to turn
the problem around. The recipe tells you how to permute
N elements if only you had a method for permuting N-1,
which you could do if you had a method for N-2, and so
on. Eventually you get down to "If only I had a method
for permuting one element," which you'll need to solve

If that's not enough of a hint, you haven't been
remedial help.

--
Eric sosman
lid

Eric Sosman, May 26, 2007
5. osmiumGuest

"osmium" writes:

>
>> Suppose we are having 3 variables...a,b,c
>> And we want to print the permutations of these variables...Such
>> as...abc,acb,bca...all 6 of them...
>> But we are not supposed to do it mannually...
>>
>> I want to know that formula by which this can be possible...
>>
>> Then that program will be ok for nnumber of variables....
>> Can anyone help me for that?

>
> This might help
>
> http://en.wikipedia.org/wiki/Permutations#Permutations_in_computing
>
> It seems to have some "Pascalish" looking source code.
>
> Because of the difficulties of handling templates, I would expect the
> source code used by next_permutation ( or whatever) is in the \include\
> directory of your compiler. I never actually looked, though.

The OP is flitting around amongst newsgroups, thus the C++ answer in a C
newsgroup. Sorry. The answer is formed with respect to a question and
answer the OP got a few days ago.

osmium, May 26, 2007
6. Malcolm McLeanGuest

news:...
> Suppose we are having 3 variables...a,b,c
> And we want to print the permutations of these variables...Such
> as...abc,acb,bca...all 6 of them...
> But we are not supposed to do it mannually...
>
> I want to know that formula by which this can be possible...
>
> Then that program will be ok for nnumber of variables....
> Can anyone help me for that?
>

You've got N! permutations of a string.
So the manual approach breaks down at about 6, the computer approach at
something like N=15.

As the said, Eric Sosman bascially you need to take each element in turn,
then permute the remainder.

So code looks something like this

/*
give user a nice wrapper, permute a string to an output
*/
void permute(char *str, FILE *fpout)
{
char buff[20]; /* you will never need more than 20 characters unless you
have a really super duper computer */
strcpy(buff, "");
permuter(buff, str, fpout);
}

/*
real function is recursive. We print a prefix
*/
static void permuter(char *prefix, char *str, FILE *fp)
{
/* check for strings of length 1, print them (with prefix), and terminate
*/

/* take each element of the string, add it to the prefix, then
call permuter() on the remaining elements */
}
--
Free games and programming goodies.
http://www.personal.leeds.ac.uk/~bgy1mm

Malcolm McLean, May 26, 2007