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
_______________________________________________
use-livecode mailing list
use-livecode@lists.runrev.com
Please visit this url to subscribe, unsubscribe and manage your subscription
preferences:
http://lists.runrev.com/mailman/listinfo/use-livecode
