permuting a string (was Re: Speed)

[Beat Cornaz]

Sat, 30 Aug 2014 09:01:16 -0400
From: Geoff Canyon 

> This was my initial thought as well, but I didn't like having to work line-by-line on (potentially) large sets of lines from the initial
> not-duplicate set of permutations. Doing the dupes first is weirder conceptually, but it means that the line-by-line work is done on a much
> smaller data set. For example, permuting "aaaabbbbcdef" would only require line-by-line on 8!/(4!*4!) = 70 lines. It will be interesting comparing the
> two solutions.

I agree, that it would be great if we can avoid working line by line. That is the beauty of Geoff's script for non duplicates, to be able to replace each distractive element in the whole bunch at the same time. This is not possible anymore, as soon as there are duplicate elements in the Permutations.

But I agree, doing the duplicates first is faster. But on a par with the script I had, which works line by line and after each new element, deletes the duplicate permutations. So dos it all in one.
On my computer : 
Input : 111222333456  		8320	 mSec	
Input : 111112222233		58	mSec	

I've trying to figure out something to keep the principle of Geoff to replace each char in the whole bunch at the same time. Either I come up with too many elements (e.g. 112  new element 3 >  31312), OR
if I use another number (char) for the duplicates, i cannot delete the duplicate permutations and end up with the same amount as if there were no duplicate elements in the input.
I also cannot replace the duplicate element temporarily, (like replace 11 with 1a : 112 > 1a2, as the duplicate 1 occurs in all the combinations (like 121). Still I feel there must be some clever trick to get it to work, but I am not completely sure.



This is my fastest script so far :

The script first orders the input elements in order of the amour of duplicate occurrences.

function BC4_PermMech_Duplicates_Chars ToPermutate
   set cursor to busy
   
   -- ** order input according to most duplicates to least duplicates
   
   replace cr with comma in ToPermutate
   put BC2_CalcNumOccurancesAll_Items (ToPermutate) into tTable
   sort lines of tTable numeric ascending by item 1 of each
   sort lines of tTable numeric descending by item 2 of each
   
   repeat for each line rLine in tTable
      repeat item 2 of rLine
         put item 1 of rLine  after ToPermutateOrdered
      end repeat
   end repeat
   
   
   put empty into TempPerms2
   put the number of items of ToPermutateOrdered into NumElements
   
   put char 1 of ToPermutateOrdered &  char 2 of ToPermutateOrdered  into TempPerms1
   put char 3 to -1 of  ToPermutateOrdered into tInput3
   put 3 into Index
   
   repeat for each char rNewElement in tInput3
      put empty into TempPerms2
      
      put the number of chars of line 1 of TempPerms1  into NumChars
      
      repeat for each line rLine in TempPerms1
         put rNewElement & rLine & cr after TempPerms2  
         
         repeat with x = 1 to NumChars 
            put char 1 to x of rLine & rNewElement & char x+1 to -1 of rLine & cr after TempPerms2
         end repeat
         
      end repeat
      
      delete char -1 of TempPerms2
      put BC2_DeleteEmptyLines_LooseOrder (TempPerms2) into TempPerms1
   end repeat
   
   choose browse tool
   
   -- ** Final deletion of duplicates
   
   return BC2_RemoveDuplicate_LooseOrder_Lines (TempPerms1)  
   
end BC4_PermMech_Duplicates_Chars 


Cheers, Beat