Sane

So if you wanted to use the more 'standard' permute algorithm, as is the one I posted, but need the signature to be: void permute(char[] str, int low, int high). You will notice the address of "r" is not changing each recursion. All you need to do is make r a global variable or accessable by the class. That leaves you with the same format for the prototype: void permutate(char *s, int k, int n).

If your algorithm works, it may be more obfucated (or difficult to prove its correctness), but it's certainly more clever. I've never seen a permutation done by swapping characters repeatedly. Where did you get the idea from?

titaniumdecoy

Well, the idea for swapping characters came from the method signature constraint. After thinking about the problem for a long time, I decided that it couldn't be done without modifying the array in some way so that's what I did. It's not that complicated either; basically, I move each character in the string to the beginning and recurse through the rest of the string in the same way. Although since I have to create n copies of the string (where n is number of characters remaining) on each recursive call, it certainly isn't suitable for large strings.

Also, I still don't understand how your method works. Could you explain it a little more? Thanks.

Sane

Well the memory is still freed every time you back edge. So, at most you only ever have as many as n strings in memory. Which isn't bad considering there are even more than n number of permutations.

Sane

The first step is to look at tree that's required to be made...



Where each node denotes a character in the result string, r, and the current depth of the tree is the index in the string.

So, for example, if we follow down the right-most path.


Therefore, r = "cba".

But how do we make this tree? As I said, the key is to keep track of what nodes have already been visited. This is, in a way, the "chalk" approach that I said in my second post, and is the only other "fast" approach to permuting a string.

You keep track of what nodes have already been visited before it. That is my "new_s" variable, which represents visited nodes by using the null terminator, so that they will not be visited again. This could also be viewed as a deletion process, to form a "new string" to be permuted.

But what's most important to realize is that we are only keeping track of what nodes have been visited in a level above the current node. It does not include nodes on the same level in a different branch. That implies that we can't share chalk between nodes. Each node has its own set of memory for what nodes have already been visited. Thus, creating new strings is the only way this can be done efficiently, because the problem consists of subproblems of a dynamic nature.

Edit: So the character swapping seems to be a popular replacement for chalk. But in essence, the same thing is done, only its less obvious about its correctness. Note that new strings are still made in this example as well. http://www.cprogramming.com/challenges/permutesol.html But it's nothing to worry about. You get n strings of n length. That's <1MB of ram for a 1000 character string. And I don't see why you would ever permute something of that size.

mbd

so are you trying to reverse the string or to create every permutation?

Sane

There was a typo in his initial post. He said "reverse" when he meant "recurse". That is what threw the first 10 posts in an alternate direction.

titaniumdecoy

Yeah... sorry 'bout that. I'll be more careful when I describe the problem next time.

mbd

i wanted to tell you about the internals of the c++ next_permutation algorithm because it does some things which the recursive algorithm will not. it recognizes that "aaa" has only identical permutations. i found this article which explains permutations pretty well. i thought you might find it interesting as well.

pushkarajthorat

This problem came into my way many times. For such, first algorithm designing should be done it helps...

__________________
[Pushkaraj]


Imagination is more important than knowledge – Albert Einstein