permuting a string (was Re: Speed)

[Alex Tweedly]

On 27/08/2014 14:33, Beat Cornaz wrote:
>
> So, getting rid of the duplicates inside the script is quite important. I still don't see yet how I can do that in Geoff's script (I will look into that again, as soon as I can find a little time). If we can get that to work, I think we'll have a winner :-)
>
>
OK, I confess I haven't been following this thread properly.
I tried to go read it all in Nabble, and failed - so my understanding 
is, erm, incomplete :-)

But I think the problem is to create all permutations of a set of input 
chars, and deal with duplicates.

So here (below) is my version (or rather, my two versions ...)

pSimple() is the simple, obvious recursive function.

It works, doesn't handle duplicates (so that would need to be done as a 
post-process, as discussed earlier) - and it's pretty slow; takes 43729 
msecs for 10 characters, exactly the same time with duplicates

permut() is the optimized version - optimize simepl cases of 1 or 2 
chars, eliminate duplicates as we go.
It works, in the no-duplicate case ("abcdefghij") it takes 23057 msecs
in the mildly duplicate case ("abcdabcdab") it takes 193 msecs
and in the heavily duplicate case ("abbbbbbbbb") it takes < 1 msec


To make it faster, it *should* be serialized, so that it isn't actually 
recursive; that should be quite easy (but will make the code much less 
easy to read or understand, so I haven't done it yet).  If you think 
it's worth pursuing, let me know and I'll have a go at unrolling the 
recursiveness.

-- Alex.

function pSimple pMute
    if the number of chars in pMute = 1 then return pMute

    put empty into t3
    repeat with i = 1 to the number of chars in pMute
       put char i of pMute into c
       put pMute into temp
       delete char i of temp
       put pSimple(temp) into t2
       repeat for each line L in t2
          put c & L & CR after t3
       end repeat
    end repeat
    return t3
end pSimple

function permut pMute
    if the number of chars in pMute = 1 then return pMute
    if the number of chars in pMute = 2 then
       return pMute & CR & char 2 of pMute & char 1 of pMute
    end if

    put empty into t3
    put empty into tDone
    repeat with i = 1 to the number of chars in pMute
       put char i of pMute into c
       if c is among the chars of tDone then next repeat
       put c after tDone
       put pMute into temp
       delete char i of temp
       switch the the number of chars in temp
          case 1
             put temp into t2
             break
          case 2
             put temp & CR & char 2 of temp & char 1 of temp into t2
             break
          default
             put permut(temp) into t2
       end switch
       repeat for each line L in t2
          put c & L & CR after t3
       end repeat

    end repeat
    return t3

end permut