permuting a string (was Re: Speed)

[Geoff Canyon]

On Mon, Sep 1, 2014 at 10:32 AM, Beat Cornaz <B.Cornaz at gmx.net> wrote:

> This is my fastest script so far :
>

I think this is faster for many arguments. It might be slower for others. I
removed the dependency on an external routine for removing duplicates. It
also removes duplicates only when needed, and event then not always (it's
expensive, so it's better to let some duplicate permutations sneak in and
then remove them all together).

I also made the (unsafe) assumption that the arguments would come already
ordered from most common to least.

I also think the original routine wouldn't work with non-duplicate values.
Try permuting "123" to see. This routine handles those correctly as far as
I've tested.

Sorry for the limited comments on the optimizations. Also, I haven't tested
each individual optimization for whether it actually speeds things up.


function beatPermut ToPermutateOrdered
   -- assumes the paramter is in decreasing order of frequency
   -- "11122334" is fine
   -- "11222" might work
   -- "12213" will probably fail

   put char 1 of ToPermutateOrdered into lastChar

   -- start with the longest string of duplicates possible
   repeat with i = 1 to length(ToPermutateOrdered)
      if char i of ToPermutateOrdered <> lastChar then exit repeat
      put char i of ToPermutateOrdered after TempPerms2
   end repeat
   put length(TempPerms2) into numChars
   put char numChars + 1 to -1 of  ToPermutateOrdered into tInput3
   put true into wasNewElement

   repeat for each char rNewElement in tInput3
      put rNewElement <> lastChar into isNewElement
      -- remove duplicates for each new value after a duplicate
      if isNewElement and not wasNewElement then
         split TempPerms2 using cr as set
         put the keys of TempPerms2 into TempPerms1
      else
         put TempPerms2 into TempPerms1
      end if
      put rNewElement into lastChar
      put empty into TempPerms2

      if isNewElement then
         -- for the first of a duplicate
         -- or for a unique
         -- just distribute it
         repeat for each line rLine in TempPerms1
            put rNewElement & rLine & cr after TempPerms2
            repeat with x = 1 to NumChars - 1
               put (char 1 to x of rLine) & rNewElement & (char x+1 to -1
of rLine) & cr after TempPerms2
            end repeat
            put rLine & rNewElement & cr after TempPerms2
         end repeat
      else
         -- for duplicates after the first
         -- never place before the first
         -- never insert except at the end of a string
         repeat for each line rLine in TempPerms1
            repeat with x = offset(rNewElement,rLine) + 1 to NumChars
               if char x of rLine <> rNewElement then put (char 1 to x-1 of
rLine) & rNewElement & (char x to NumChars of rLine) & cr after TempPerms2
            end repeat
            put rLine & rNewElement & cr after TempPerms2
         end repeat
      end if
      add 1 to NumChars
   end repeat

   -- Final deletion of duplicates, if the last element was a duplicate
   if isNewElement then return TempPerms2
   split TempPerms2 using cr as set
   return the keys of TempPerms2
end beatPermut