Speed

[Beat Cornaz]

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