Hatrack River Forum: Need hints recursively permuate a string

This is topic Need hints recursively permuate a string in forum Books, Films, Food and Culture at Hatrack River Forum.

To visit this topic, use this URL:
http://www.hatrack.com/ubb/main/ultimatebb.php?ubb=get_topic;f=2;t=048164

Posted by Blayne Bradley (Member # 8565) on :

Say I have an array Alpha in which is A-Z

I input N into the program and it grabs the first N letters.

And puts them into say Beta[ N-Nth ]

and heres a function

something Perm ( char [] );

so basically I need to code a function that will calc recursively every posible permutations of the array passed to it.

So, what kind of data type would I use to be able to return an array?

Somethng Perm ( char [] )
{

return Perm ( array )
}

Any hints in regards to logic and any help in regards to syntax?

Posted by TrapperKeeper (Member # 7680) on :

23.

Posted by Blayne Bradley (Member # 8565) on :

I thought it was 42.

Posted by Dagonee (Member # 5818) on :

Blayne, do this:

make a spreadsheet with the letters ABCD each in a different cell in the top row.

Then manually go through and develop all the permutations.

Then go back and do it again, this time thinking about what you're doing and why you're doing it - particularly the order in which you're doing it.

Write that out in pseudocode and post it here.

I'm willing to help out with some logic, but you need to practice trying to do it on your own - before even trying to write any code.

Posted by Dagonee (Member # 5818) on :

It might also be easier for you to do it with squares of paper cut out with letters on them. It depends on how you think best.

Posted by Blayne Bradley (Member # 8565) on :

for ABC

ABC BAC CBA
ACB BCA CAB

6 permutations.

Since n = 3 if i were to use

code:

int Facts ( int n )
{
    if ( n == 0 )

        return 1;

    else

        return n * Facts( n - 1 );

}

This tells me the total number of permutations which I think would be useful for a loop.

Basically I know I need to make 1 function that will call itself.

as for ABC well theres 3 letters.

ABC

so take A

A then theres 2 letters, since we alrdy have a permutation with ABC just take 2 letters past A and switch them.

if no other permutations can be done increment to the next letter.

ABC

now were at b, so swap A and B.

BAC, gives us a new permutation

and then the next 2 numbers so BCA

rinse and repeat.

This is simple enough ild imagine an outer and inner loop would do Im just wondering how do it recursively.

Posted by fugu13 (Member # 2859) on :

Think of it this way. Given a string of six characters, if you pick one, all possible permutations starting with that character are found by appending all possible permutations of the other five characters to that character.

So, all possible permutations of six characters can be found by iteratively picking each of the characters to be the first character, and finding all possible permutations of the other five (and appending them to the chosen first character. Think about that.

That makes me think of something interesting. It would be possible to do some really cool template generation to make permutation generation (up to any arbitrary length of string) extremely fast -- after all, you can think about any string as having an ordering, and then to generate permutations all you need are the permutations of the ordering, which can be easily pregenerated with templates; then its just a matter of sticking a string in what's essentially a completely unrolled permutation loop and getting the results.

Posted by mr_porteiro_head (Member # 4644) on :

Awesome.

Posted by xnera (Member # 187) on :

quote:
That makes me think of something interesting. It would be possible to do some really cool template generation to make permutation generation (up to any arbitrary length of string) extremely fast -- after all, you can think about any string as having an ordering, and then to generate permutations all you need are the permutations of the ordering, which can be easily pregenerated with templates; then its just a matter of sticking a string in what's essentially a completely unrolled permutation loop and getting the results.

*swoons*