All right, the permutations. Thanks for the responses.
My findings so far :
Mark wrote :
--
In addition, you're losing much of the speed of the "repeat for each"
loops by embedding a "repeat with" loop at the deepest level (and in
addition you're making an unneccsary extra copy of tLine each time
through the slowest loop):
repeat for each line tLine in TempPerms1
repeat with y = Index down to 1
put tLine into Temp
put newElement & comma before item y of temp
put Temp & cr after TempPerms5
end repeat
end repeat
Something like this should be faster (do this for both upper and lower
halves):
repeat for each line tLine in TempPerms1
repeat for each item tItem in tLine
put tItem & comma after TempPerms5
end repeat
put cr into char -1 of TempPerms5
end repeat
--
Mark, I cannot get your improvement to work. I think there is something missing
or maybe I am overseeing something.
The inner loop in your script is equivalent to : put tLine into TempPerms5.
The total result from the inner & outer loop is the same as : put TempPerms1
into TempPerms1
As a total result of the complete script I always get (no matter what the input
is) : 1,2 cr 2,1
In my script, I need to ' put tLine into Temp' in every time I pass the inner
loop, to renew Temp with tLine. Otherwise I change tLine all the time in the
inner loop. In every round in the outer loop, I step the new element (e.g. 3)
through all possible positions in tLine (e.g. tLine = 1,2 > 1,2,3
1,3,2 3,1,2 ) . Then I go on and do the same with the next element (4 in
this case) for each newly formed line (1,2,3 etc).
----
Dick wrote : The Wikipedia entry for "permutation" says the fastest algorithm
for generating permutations is Heap's algorithm.
Quite interesting. I still have to understand what's happening completely, but
I implemented you LC translation of the Heap algo. And it runs on my system a
bit over 2 minutes (165732 millisecs) for 10 elements.
To my surprise, my old algo does it in 7515 millisecs. I could improve on that
by using chars instead of items (7465 millisecs).
Another improvement I could make was by only calculating the upper half of the
permutations (all the ones that start with 1,2,) and then copy them and swap
the 1's and 2's. This gave as result only 5597 millisecs for 10 elements.
I am a bit at a loss, as I would be surprised if my way would be like 25 times
faster than the fastest known algorithm. Did I make a mistake in implementing
Dicks code (although
Dick also reports 2 minutes to do the job, as my way does it in 5.6 secs). What
is happening here.
I even suspect, that I can improve more on my improved way (by only calculating
half of the perms and swapping the 1's and 2's. I might apply that principle
more (like only calculating 1/4 of the perms and do some swapping, or even
better). I will look into that later.
---
Kay wrote :
I obtained a 10% speed increase by changing this:
repeat with n = 3 to 10
to this:
put "3,4,5,6,7,8,9,10" into nList
repeat for each item n in nList
I haven't been able to try this, but it is very interesting in general. That
even such short lists produce such a difference in speed in repeat with or
repeat for. I thought that only counted for longer lists. very enlightening
though. Thanks.
---
Geoff : looks promising. It is in the ballpark where my alto seems to be. I
will get back to you letter when I have had a good look and test at your script.
New idea :
I was hinting at a way of producing permutations in the case that there are
duplicate elements in the input. F.i. 1,1,2,3 only gives 12 permutations
instead of 24 for 1,2,3,4 as input.
Before I calculated all the possible permutations and deleted the duplicates
afterwards. I found that if I move the removing of duplicates to an early stage
(as early as possible), the speedup is enormous.
Thanks for all the input,
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
