permuting a string (was Re: Speed)

[Alex Tweedly]

(second reply ..)

On 27/08/2014 21:15, Beat Cornaz wrote:
> Alex wrote :
>
> Recursive scripts is something I know in principle about, but never have used them before. They are quite compact, but I find it hard to follow, especially as your variables are emptied in each new entry into the script (f.i. t3 in Alex's script).
> I tried to unroll it and make it serial, but I am having troubles with it. I think I should start in the opposite direction and work back, but it's too late now for me to solve it. First a little sleep.
> I also tried to serialise Geoff's script, but am running into the same difficulty. I haven't grasped the concept completely I guess.
>
> If you could give me a hint, Alex, I'd be happy.
>
Thoinking about recursive scripts can be very hard ..... but often 
thinking about problems and recursive solutions is easy (i.e. solutions 
not scripts).

So don't get bogged down in the details of the script - think about what 
it's doing at the abstract level.

You want to permute a set of characters. So you take each possible 
character in turn to be the first character of the (partial) answer, and 
follow it by all permutations of the remaining characters. (That's it - 
that's all you're trying to do :-)

Oh - except for the terminal case where there is only one character - 
when the answer is that single character.

so the pseudo-code is just

    repeat with i = 1 to the number of chars in the string
        get a copy of the string with "char i" deleted
        recursively get the result for that
        put char i at the front of each line of that result
    end repeat

As for "variables are emptied" - I don't think of it that way, I think 
of it as : a recursive function is typically "pure", uses neither global 
nor script-local variables - the only contact with the rest of the world 
is the parameters passed in and the result passed back.

I'm sure there are cases where recursive functions use globals (or 
script-locals), but that's usually a recipe for confusion in a recursive 
world. When you try to "de-recurse" the function - i'e' serialize it - 
you usually finish up with variables that are building up the partial 
results and/or the state of the working - and that can be confusing.

I'll have a go at serializing this code - hopefully tonight (i.e. 
starting now and not getting myself tied up in knots with it :-)

-- Alex.