it's not far off it. Stefan has actually written it as a command-line app with no interface. But if he put it in a class of its own and saved it as a framework, then yes it would. And if "put it in a class of its own and saved it as a framework" sounds complicated, it's actually very simple.

This is an example of how such code can be made accessible to AS:

www.macosxautomation.com/applescript/ap … xtras.html

It's just bits of Objective-C that do some common task that AS is slow at, put together in a single class and saved as a framework.

here's the AppleScriptObjC version as Script Library of the Heap's algorithm which is supposed to be the fastest according several sources.
However it's dramatically slower than the pure ObjC version.
It takes 0,022 s for 5 and 219 secs for 9 elements

Applescript:

use framework "Foundation"

property inputArray : missing value
property outputArray : missing value


on heapPermute(n)
   if n = 1 then
       outputArray's addObject:inputArray
   else
       repeat with i from 1 to n
           heapPermute(n - 1)
           if (n mod 2 = 1) then
               (inputArray's exchangeObjectAtIndex:0 withObjectAtIndex:(n - 1))
           else
               (inputArray's exchangeObjectAtIndex:(i - 1) withObjectAtIndex:(n - 1))
           end if
       end repeat
   end if
end heapPermute

on permute(theList)
   set inputArray to current application's NSMutableArray's arrayWithArray:theList
   set outputArray to current application's NSMutableArray's array()
   heapPermute(count inputArray)
   return outputArray as list
end permute

Thanks for all your helpful replies and suggestions, Shane — and of course for your definitive beginners' book about ASObjC, of which I gather there's soon to be a second edition covering the changes in Yosemite? 

Hello, I feel this is the right place for having methods that also counts the number of permutations/combinations to generate, or having generated. Actually, the methods I posted above are pretty much dependent on those, so why not have them in the same thread.

The factorial handler, tells how many permutations you get out of a set of n objects.

The C handler (or binomial coeffecient) tells how many r combinations you get out a set of n elements. Another way to say this is, how many ways can I generate a subset with r elements, when order doesn't matter,  out of a set with n elements.

The P handler tells how many r permutations out of a set of n elements you can generate. (subsets with r elements out of a set of n elements).

Applescript:

on factorial(n)
   if n > 170 then error "Factorial: n too large."
   # Result greater than 1.797693E+308!
   if n < 0 then error "Factorial: n not positive."
   set a to 1
   repeat with i from 1 to n
       set a to a * i
   end repeat
   return a
end factorial


on C(n, r)
   # Counts the number of r-combinations in a set of n elements.
   # it is also called the binomial coeffecient.
   if n = 0 or n < r or r < 0 then error "C: argument error"
   return (factorial(n) div (factorial(r) * (factorial(n - r))))
end C

on P(n, r)
   # counts the number of r-permutations in a set of n elements.
   if n = 0 or n < r or r < 0 then error "P: argument error"
   
   return (factorial(n) div (factorial(n - r)))
   
end P

Edit
Made boundary tests, slightly more correct, as r is now allowed to be  zero.

Last edited by McUsrII (2014-10-07 06:47:51 am)

Since we're involving other programming languages, native C does it in 15ms, for 9 items.

Got it. :-)

Nigel,

Am I right in assuming you're using a script object because that's what you need to do with long AS lists? If so, there's no need in the ASObjC version. I rewrote it without it, and I think it's a little bit faster, but I'd be interested in your time:

Applescript:

use AppleScript version "2.3.1"
use scripting additions
use framework "Foundation"

on prmt(l, workArray, permutations)
   -- l is the zero-based index of the leftmost item affected by this iteration
   set r to (workArray's |count|()) - 1
   set m to r - 1
   set n to r - l + 1 -- n is the number of list items affected by this iteration (l thru r)
   
   if (n is 3) then
       -- These six permutations are hard-coded to reduce low-level recursion
       permutations's addObject:(workArray's |copy|())
       
       workArray's exchangeObjectAtIndex:r withObjectAtIndex:m
       permutations's addObject:(workArray's |copy|())
       
       workArray's exchangeObjectAtIndex:r withObjectAtIndex:l
       permutations's addObject:(workArray's |copy|())
       
       workArray's exchangeObjectAtIndex:r withObjectAtIndex:m
       permutations's addObject:(workArray's |copy|())
       
       workArray's exchangeObjectAtIndex:r withObjectAtIndex:l
       permutations's addObject:(workArray's |copy|())
       
       workArray's exchangeObjectAtIndex:r withObjectAtIndex:m
       permutations's addObject:(workArray's |copy|())
   else
       -- Precalculate some values for the repeat
       set lPlus1 to l + 1 -- parameter for next-level recursions
       set nIsEven to (n mod 2 = 0) -- true if n is even
       set x to r -- the default index with which to swap if n is odd
       
       -- Get all permutations of items (l +1) thru r with the current item l
       prmt(lPlus1, workArray, permutations)
       -- Repeat with successive values of item l
       repeat with i from r to lPlus1 by -1
           -- If n is even, swap items l and i, otherwise default to swapping items l and r
           if (nIsEven) then set x to i
           (workArray's exchangeObjectAtIndex:x withObjectAtIndex:l)
           prmt(lPlus1, workArray, permutations)
       end repeat
   end if
end prmt

on allPermutations(theList)
   set permutations to current application's NSMutableArray's array() -- the mutable array we will add to
   set workArray to current application's NSMutableArray's arrayWithArray:theList -- the starting array
   set r to (workArray's |count|()) - 1
   if (r < 2) then
       -- Special-case lists of less than three items
       workArray's addObject:theList
       if (r is 1) then permutations's addObject:(workArray's reverseObjectEnumerator()'s allObjects())
   else
       -- Otherwise use the recursive handler
       prmt(0, workArray, permutations)
   end if
   return permutations as list
end allPermutations

Hi Shane.

Your assumption's party right. As you probably noticed, my first ASObjC script (post #13) is just a revamp of my right-to-left vanilla script from post #10, with ObjC arrays and methods used instead of vanilla where there are more than two items.

In the vanilla scripts, the script-object-within-a-handler idea offers three advantages (to my way of thinking):
1. The script object's properties can be "referenced" to allow faster access to the vanilla list items.
2. The recursive part of the only-partially recursive process can be contained within the main handler.
3. The lists and the precalculated r and m values can be held in local properties instead of having to be passed or recalculated with each recursion or held in globals or global properties outside the main handler.

Point 1, as you say, doesn't apply with the ObjC arrays. Point 2 is a largely a matter of my own personal preference. Point 3 is connected with point 2, but is also relevant with regard to the amount of work the script has to do. Your rewrite passes two extra parameters AND recalculates r and m on every call to the recursive handler. I'd therefore expect it to be a little slower than my script. And it is, on my machine. With nine items, it's taking about six seconds longer than mine this morning. But mine's taking a fair bit longer than it did yesterday, so the difference between the scripts' times may actually be less under optimal conditions.

Now that's interesting! But the difference is far less dramatic for me. 117 seconds as opposed to 134 (this morning). Still, that's a lot more than I'd have expected until you mentioned it.

Exactly! Nigel's code took 45 seconds on my MBP when an AppleScript list is returned but when I return a pointer to the NSMutableArray it took only 40 seconds. That means that AppleScriptObjC bridge will take up to 5 seconds to coerce to a NSMutableArray containing 362,880 items into an AppleScript list. That fits right with my OSAX "problem" because when thinking about it, the AEPutParamDesc does an extra copy of the object meaning it will take two times 5 seconds (and probably some more copying when the event is handled by the event manager).

AppleScript allows lists up to 2^31 items, well at least in theory. Because the maximum allowed index is the maximum value of a signed 32-bit integer and negative indexes are not allowed. To create a list with 362880 items, there is no problem you just have to wait 20+ seconds.

Last edited by DJ Bazzie Wazzie (2014-10-08 08:26:52 am)

Hello.

For those interested, here is a generator of r-combinations. There is nothing wrong with Daehls, I just wanted something simpler to understand as the problem intrigued me, so this is probably slower. I found the pseudo code in a buggy! pdf document somwhere.  (Daehls delist handler is something that seems to be a great way to translate items into indicies IMO.)

Applescript:

set comboList to {}
combination(comboList, 3, 6)
listprint(comboList)
(*
"{1, 2, 3}
{1, 2, 4}
{1, 2, 5}
{1, 2, 6}
{1, 3, 4}
{1, 3, 5}
{1, 3, 6}
{1, 4, 5}
{1, 4, 6}
{1, 5, 6}
{2, 3, 4}
{2, 3, 5}
{2, 3, 6}
{2, 4, 5}
{2, 4, 6}
{2, 5, 6}
{3, 4, 5}
{3, 4, 6}
{3, 5, 6}
{4, 5, 6}"
*)
on combination(combinations, r, n)
   # print the first r combination
   set S to {}
   repeat with i from 1 to r
       set end of S to i
   end repeat
   copy S to end of combinations
   
   repeat with i from 2 to C(n, r)
       set m to r
       set max_val to n
       
       repeat while (((item m) of S) = max_val)
           set m to m - 1
           set max_val to max_val - 1
       end repeat
       # increment the above rightmost element
       set item m of S to (item m of S) + 1
       # all others are the successors:
       
       repeat with j from (m + 1) to r
           set item j of S to (item (j - 1) of S) + 1
       end repeat
       copy S to end of combinations
   end repeat
end combination


on listprint(theL)
   try
       text 0 of theL
   on error e
       set ofs to offset of "{" in e
       set tmp to text (ofs + 1) thru -3 of e
       tell (a reference to text item delimiters)
           set astid to contents of it
           set contents of it to "}, "
           set newl to text items of tmp
           set contents of it to "}" & return
           set newt to newl as text
           set contents of it to astid
       end tell
       return newt
   end try
end listprint


on C(n, r)
   # Counts the number of r-combinations in a set of n elements.
   # it is also called the binomial coeffecient.
   if n = 0 or n < r or r < 0 then error "C: argument error"
   return (factorial(n) div (factorial(r) * (factorial(n - r))))
end C


on factorial(n)
   if n > 170 then error "Factorial: n too large."
   # Result greater than 1.797693E+308!
   if n < 0 then error "Factorial: n not positive."
   set a to 1
   repeat with i from 1 to n
       set a to a * i
   end repeat
   return a
end factorial

Edit
Made a "fancier" listprint handler.

Last edited by McUsrII (2014-10-08 02:36:58 pm)

Here's an interesting one.

By means of concatenation, this vanilla version of my script prebuilds a list of the required length to hold the permutations. When used as a Library in exactly the same way as the ASObjC version in post #13, it executes in a mere 5 seconds or so as opposed to the ASObjC version's 134 seconds! However, with both versions, it then takes nearly two and a half minutes to do anything with the result, such as setting a variable to it or getting its class!

Applescript:

on allPermutations(theList)
   
   script o
       property workList : missing value
       property permutations : {}
       property r : count theList -- index of the rightmost item of workList.
       property m : r - 1 -- index of the middle item of the last three of workList.
       property p : 1 -- index into the permutations list.
       
       on prmt(l)
           -- l is the index of the leftmost item affected by this iteration
           set n to r - l + 1 -- n is the number of list items affected by this iteration (l thru r)
           
           if (n is 3) then
               -- These six permutations are hard-coded to reduce low-level recursion
               copy my workList to item p of my permutations
               
               set {v1, v2, v3} to items l thru r of my workList
               
               set item m of my workList to v3
               set item r of my workList to v2
               copy my workList to item (p + 1) of my permutations
               
               set item l of my workList to v2
               set item r of my workList to v1
               copy my workList to item (p + 2) of my permutations
               
               set item m of my workList to v1
               set item r of my workList to v3
               copy my workList to item (p + 3) of my permutations
               
               set item l of my workList to v3
               set item r of my workList to v2
               copy my workList to item (p + 4) of my permutations
               
               set item m of my workList to v2
               set item r of my workList to v1
               copy my workList to item (p + 5) of my permutations
               
               set my p to p + 6
           else
               -- Precalculate some values for the repeat
               set lPlus1 to l + 1 -- parameter for next-level recursions
               set nIsEven to (n mod 2 = 0) -- true if n is even
               set x to r -- the default index with which to swap if n is odd
               
               -- Get all permutations of items (l +1) thru r with the current item l
               prmt(lPlus1)
               -- Repeat with successive values of item l
               repeat with i from r to lPlus1 by -1
                   -- If n is even, swap items l and i, otherwise default to swapping items l and r
                   if (nIsEven) then set x to i
                   tell item x of my workList
                       set item x of my workList to item l of my workList
                       set item l of my workList to it
                   end tell
                   prmt(lPlus1)
               end repeat
           end if
       end prmt
       
   end script
   
   if (o's r < 3) then
       -- Special-case lists of less than three items
       copy theList to the beginning of o's permutations
       if (o's r is 2) then set the end of o's permutations to the reverse of theList
   else
       -- Otherwise use the recursive handler
       copy theList to o's workList
       -- Prebuild a list of the required length (factorial of theList's length) to hold the permutations.
       set mv to missing value
       set mvList to {mv, mv, mv, mv, mv, mv} -- Minimum length is 6 with a 3-item input list.
       set mvList2 to mvList
       repeat with i from 3 to (o's r) - 1
           repeat i times
               set mvList2 to mvList2 & mvList
           end repeat
           set mvList to mvList2
       end repeat
       set o's permutations to mvList
       o's prmt(1)
   end if
   
   return o's permutations
   
end allPermutations