permuting a string (was Re: Speed)

[Alex Tweedly]

On 27/08/2014 23:02, Alex Tweedly wrote:
>
> 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 :-)
>
Here's a serialized version. Not as fast as I had hoped - it's about 
twice as fst as the recursive vesion, but that means the non-duplicate 
case ("abcdefghij") still takes about 13000ms, while the duplicated 
versions are ("abcdabcdab") = 180 msec and "abbbbbbbbb" < 0

Remember .... I didn't say this code would be clear :-)

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

    put empty into tOutput
    -- an entry has
    --     item 1 is a prefix
    --     item 2 is the remaining set of chars to permute
    --  tOutput contains the result of the permutation

    put TAB & pMute &CR into todo

    set the itemdel to TAB
    repeat
       if todo is empty then exit repeat
       put todo into tDoing
       put empty into todo
       repeat for each line L in tDoing
          put item 1 of L into tPrefix
          put item 2 of L into tPerm

          switch the number of chars in tPerm
             case 1
                put tPrefix & tPerm & CR after tOutput
                break
             case 2
                put tPrefix & tPerm & CR after tOutput
                if char 1 of tPerm <> char 2 of tPerm then put tPrefix & 
char 2 of tPerm & char 1 of tPerm & CR after tOutput
                break
             default
                put empty into tDone
                repeat with i = 1 to the number of chars in tPerm
                   put char i of tPerm into c
                   if c is among the chars of tDone then next repeat
                   put c after tDone

                   put char 1 to i-1 of tPerm & char i+1 to -1 of tPerm 
into temp
                   put tPrefix & c & TAB & temp & CR after todo
                end repeat -- over chars in tPerm
          end switch
       end repeat
    end repeat
    return tOutput

end serialpermut

-- Alex.