I got this far so far... it works but it's not automated enough... needs more work!

Applescript:

set L to {"a", "b", "c"}

copy L to z
set y to {}
repeat with i from 1 to count of L
   set item 1 of z to (item i of L)
   
   repeat with j from 1 to count of L
       set item 2 of z to (item j of L)
       
       repeat with K from 1 to count of L
           set item 3 of z to (item K of L)
           set end of y to (z as text)
       end repeat
   end repeat
end repeat

return y

--> {"aaa", "aab", "aac", "aba", "abb", "abc", "aca", "acb", "acc", "baa", "bab", "bac", "bba", "bbb", "bbc", "bca", "bcb", "bcc", "caa", "cab", "cac", "cba", "cbb", "cbc", "cca", "ccb", "ccc"}

I was looking for a handler to calculate combinations recently and came across this thread. I'm not sure exactly what the proper math/computer term is for the process Regulus6633 was looking for, but just as an FYI, it's not a mathematical combination.

A Combination is a unique group of items without regarding their order. So {1,2,3} and {3,2,1} are both the same combination. {1,2,3} = {3,2,1}. And each member of the original set can only be represented once in the combination. So {1,1,1} is not a valid combination of {1,2,3}.

A Permutation is a group of items where order is important. So {3,2,1} is a unique permutation of {1,2,3}, and so is {2,1,3} etc. Again, the mathematical definition of permutations also requires that each member of the original set be represented just once in the permutation. So {1,1,1} is not a permutation of {3,2,1}.

Anyway, I realize that Regulus6633 was looking for something different, but just in case anyone else is looking for combination & permutation handlers, as I was, here are some. I had searched throughout MacScripter and other AppleScript sites and was surprised I couldn't find any. So it was a fun exercise porting these to AppleScript by using pseudo code I found while Google'ing. I'm also posting them to RosettaCode.net (a cool site I stumbled upon recently and could really use more AppleScript contributions, I'm doing my best to represent!):

Applescript:

on combinations(theList, k)
   script combinations
       on next_comb(c, k, n)
           set i to k
           set c's item i to (c's item i) + 1
           repeat while (i > 1 and c's item i ≥ n - k + 1 + i)
               set i to i - 1
               set c's item i to (c's item i) + 1
           end repeat
           if (c's item 1 > n - k + 1) then return false
           repeat with i from i + 1 to k
               set c's item i to (c's item (i - 1)) + 1
           end repeat
           return true
       end next_comb
       on delist(theList, theIndexList)
           repeat with i in theIndexList
               set i's contents to theList's item (i's contents)
           end repeat
           return theIndexList
       end delist
   end script

   set {c, r} to {{}, false}
   if class of theList = list then set {n, l} to {length of theList, true}
   if class of theList is in {real, integer} then set {n, l} to {theList as integer, false}
   if 0 < k and k ≤ n then
       repeat with i from 1 to k
           set end of c to i's contents
       end repeat
       if l then set r to {combinations's delist(theList, c's contents)}
       if not l then set r to {c's contents}
       repeat while combinations's next_comb(c, k, n)
           if l then set end of r to combinations's delist(theList, c's contents)
           if not l then set end of r to c's contents
       end repeat
   end if
   return r
end combinations

return combinations(4, 3)
--> {{1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}}

return combinations({"A", "B", "C", "D"}, 3)
--> {{"A", "B", "C"}, {"A", "B", "D"}, {"A", "C", "D"}, {"B", "C", "D"}}

Applescript:

on permutations(theList)
   script permutations
       property r : {}
       property l : true
       on permute(v, start, n)
           if l then set end of r to permutations's delist(theList, v's contents)
           if not l then set end of r to v's contents
           if start ≤ n then
               repeat with i from (n) to start by -1
                   repeat with j from (i + 1) to n
                       set {v's item i, v's item j} to {v's item j, v's item i}
                       my permute(v, i + 1, n)
                   end repeat
                   set tmp to v's item i's contents
                   repeat with k from i to (n - 1)
                       set v's item k to v's item (k + 1)
                   end repeat
                   set v's item n to tmp
               end repeat
           end if
           return r
       end permute
       on delist(theList, theIndexList)
           repeat with i in theIndexList
               set i's contents to theList's item (i's contents)
           end repeat
           return theIndexList
       end delist
   end script
   
   set v to {}
   if class of theList = list then set {n, permutations's l} to {length of theList, true}
   if class of theList is in {real, integer} then set {n, permutations's l} to {theList as integer, false}
   repeat with i from 1 to n
       set end of v to i's contents
   end repeat
   return permutations's permute(v, 1, n)
end permutations

return permutations(3)
--> {{1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1}}

return permutations({"A", "B", "C"})
--> {{"A", "B", "C"}, {"A", "C", "B"}, {"B", "A", "C"}, {"B", "C", "A"}, {"C", "A", "B"}, {"C", "B", "A"}}

Model: MacBook Pro
AppleScript: 2.0.1
Browser: Safari 4.0.4 5531.21.10
Operating System: Mac OS X (10.6)

Last edited by daehl (2010-02-27 12:38:42 am)

Permutations got a brief airing on the MACSCRPT list in October/November 2004. (Subject: "Permute a list?") My own effort, if you're interested, was this.

Thanks, Nigel! Yes, I am interested, and always appreciate your contributions. And wow, is that fast!

Last edited by daehl (2010-03-02 10:14:25 am)

I still have my original scripts. The first is based directly on an algorithm in a document by Robert Sedgewick, the link to which at the top of the script still works!:

Applescript:

-- A port to AppleScript of "Improved version of Heap's method (recursive)"
-- found in Robert Sedgewick's PDF document "Permutation Generation Methods"
-- <[url]http://www.cs.princeton.edu/~rs/talks/perms.pdf[/url]>

-- Sedgewick's version recurses directly to the first three items in the list,
-- whose six possible combinations are added to the collection without further
-- recursion, presumably to combine speed with a convenient recursion exit. Any
-- further items are added into the permutation process as the recursion retreats,
-- each change of value in the current rightmost item being accompanied by all
-- possible arrangements of the items to its left. Changes to the rightmost item
-- are effected thus: at recursion levels handling an odd number of list items, the
-- rightmost item is exchanged with the leftmost item only; at recursion levels
-- handling an even number of list items, the rightmost item is exchanged with each
-- of the preceding items in turn, starting with the leftmost.
--
-- This script special-cases lists of less than three items.

on allPermutations(theList)
   
   script o
       property workList : missing value
       property permutations : {}
       property r : count theList -- index of the rightmost item
       
       on prmt(n)
           -- n is the index of the rightmost list item affected by this iteration
           -- and thus also the number of list items affected by this iteration (1 thru n)
           
           if n = 3 then
               -- These six permutations are hard-coded to reduce low-level recursion
               copy my workList to the end of my permutations
               
               set {v1, v2, v3} to my workList
               
               set item 2 of my workList to v1
               set item 1 of my workList to v2
               copy my workList to the end of my permutations
               
               set item 1 of my workList to v3
               set item 3 of my workList to v2
               copy my workList to the end of my permutations
               
               set item 1 of my workList to v1
               set item 2 of my workList to v3
               copy my workList to the end of my permutations
               
               set item 1 of my workList to v2
               set item 3 of my workList to v1
               copy my workList to the end of my permutations
               
               set item 1 of my workList to v3
               set item 2 of my workList to v2
               copy my workList to the end of my permutations
           else
               -- Precalculate some values for the repeat
               set nMinus1 to n - 1 -- parameter for next-level recursions
               set nIsEven to (n mod 2 = 0) -- true if n is even
               set x to 1 -- the default index with which to swap if n is odd
               
               -- Get all permutations of items 1 thru (n - 1) with the current item n
               prmt(nMinus1)
               -- Repeat with successive values of item n
               repeat with i from 1 to nMinus1
                   -- If n is even, swap items n and i, otherwise default to swapping items n and 1
                   if nIsEven then set x to i
                   tell item x of my workList
                       set item x of my workList to item n of my workList
                       set item n of my workList to it
                   end tell
                   prmt(nMinus1)
               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 the beginning of o's permutations
   else
       -- Otherwise use the recursive handler
       copy theList to o's workList
       o's prmt(o's r)
   end if
   
   return o's permutations
   
end allPermutations

allPermutations({1, 2, 3, 4, 5})

But I prefer this one, a modification which permutes from the right instead of from the left, giving a more ordered appearance to the results (for those of us who normally read from left to right):

Applescript:

-- A port to AppleScript of "Improved version of Heap's method (recursive)"
-- found in Robert Sedgewick's PDF document "Permutation Generation Methods"
-- <[url]http://www.cs.princeton.edu/~rs/talks/perms.pdf[/url]>
--
-- This version attempts to produces a slightly more "sorted" result than
-- Sedgewick's, by recursing directly to the *last* three items in the list, whose
-- six possible combinations are added to the collection without further recursion.
-- Any preceding items are added into the permutation process as the recursion
-- retreats, each change of value in the current leftmost item being accompanied by
-- all possible arrangements of the items to its right. Changes to the leftmost
-- item are effected thus: at recursion levels handling an odd number of list
-- items, the leftmost item is exchanged with the rightmost item only; at recursion
-- levels handling an even number of list items, the leftmost item is exchanged
-- with each of the following items in turn, starting with the rightmost.
--
-- This script special-cases lists of less than three items.

on allPermutations(theList)
   
   script o
       property workList : missing value
       property permutations : {}
       property r : count theList -- index of the rightmost item
       property m : r - 1 -- index of the middle item of the last three
       
       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 = 3 then
               -- These six permutations are hard-coded to reduce low-level recursion
               copy my workList to the end 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 the end of my permutations
               
               set item l of my workList to v2
               set item r of my workList to v1
               copy my workList to the end of my permutations
               
               set item m of my workList to v1
               set item r of my workList to v3
               copy my workList to the end of my permutations
               
               set item l of my workList to v3
               set item r of my workList to v2
               copy my workList to the end of my permutations
               
               set item m of my workList to v2
               set item r of my workList to v1
               copy my workList to the end of my permutations
           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 the beginning of o's permutations
   else
       -- Otherwise use the recursive handler
       copy theList to o's workList
       o's prmt(1)
   end if
   
   return o's permutations
   
end allPermutations

allPermutations({1, 2, 3, 4, 5})

No doubt Shane will produce an ASObjC version ere long. 

Pass.

I can see I'm going to have to take up a new hobby

I ran both versions in a similar environment, and the original was a bit above 3 times as fast for the list of 5 items. But the gap narrows as you add numbers. At 9, I got 143 seconds vs 151. So I tweaked your script a smidge, to use copy() to make the new arrays like this:

Applescript:

permutations's insertObject:(workArray's |copy|()) atIndex:len

That brought the time down to a whisker under 140. You have a winner

For the curious ones:
It so happens that I have implemented such an function in my personal OSAX, which may sound a bit unfair. Obviously, it's a C solution for AppleScript, but it's only 3 times faster than Nigel's Objective-C version (32 seconds, against 105). The bottleneck in Nigel's vanilla solution is the same as in C, copying 362,880 times to a list and place it in a growing list. The AppleScriptObjC version completely depends on AppleEvents but has no data handling on it's own. It so happens that for the first time I see that AppleScriptObjC comes close to OSAX in performance.

The permutation in this post is maybe worth to translate to AppleScriptObjC, it could avoid copying and swapping making it run a lot faster.

Last edited by DJ Bazzie Wazzie (2014-10-06 10:08:56 am)

Hello.

Here is the lexical r-permutation counterpart of the handler above, this one, takes the former permutation as an argument, and delivers the next one (in lexical order), as above, it is important to keep track of the number of calls as well, so you don't overstep the number of possible permutations.

The advantage of this approach, is to spread the cost of creating the permutations, over the run of "something".

Applescript:

(*

   Get next R permutation.
   
   Pseudo code from Kenneth. H. Rosen Discrete mathematics and its applications p. 384.

   Returns the next lexical permutation, based on the permutation passed..
    a: the former permutation
   
*)

on next_R_Permutation(a)
   
   
   set n to (length of a)
   set j to n - 1
   
   try
       repeat while (item j of a) > item (j + 1) of a
           set j to j - 1
       end repeat
   on error
       error "next_R_Permutation: Error: Passed over the last permutation"
   end try
   # j is now the largest subscript with item j of a < item (j+1) of a    
   set k to n
   
   repeat while item j of a > item k of a
       set k to k - 1
   end repeat
   (*

item k of a is now the smallest integer greater than item j of a
to the right of item j of a

*)
   local rptmp
   
   set rptmp to item j of a
   set item j of a to item k of a
   set item k of a to rptmp
   
   set r to n
   set s to j + 1
   
   repeat while r > s
       set rptmp to item r of a
       set item r of a to item s of a
       set item s of a to rptmp
       set r to r - 1
       set s to s + 1
   end repeat
   
   return a
end next_R_Permutation


# driver for next_R_permutation
(*
set m to next_R_Permutation({3, 1, 2})
--> {3,2,1}
try
   text 0 of m
on error e
   set ofs to offset of "of " in e
   display dialog (text (ofs + 3) thru -2 of e)
end try
*)

My timings were rough (and late!), but that's very interesting. I guess I'm still intrigued by why one version scales better than the other. AppleScript garbage collection is one obvious potential factor, but I wonder if there's more to it.

FYI, you can use mutableCopy() to produce a mutable copy, and both copy()/mutableCopy() can be called on either mutable or immutable objects. And not just arrays, but also string, sets -- any of the classes that have a mutable subclass.

Aha! Thanks. Now incorporated into the script above.

So in fact the initial manifestation of 'theArray' needn't be mutable. One difference between this script and my ASObjC version of "Improved Heap" is that one creates and stores mutable arrays and the other immutable ones. Does this have any implications for speed or storage?