Tuesday, August 11, 2020

You are not logged in.

**regulus6633****Member**- From:: Taulov, Denmark
- Registered: 2006-11-02
- Posts: 1695
- Website

supposed I had this list {"a","b","c"}

I want to use repeat loops and iterate that list such that I get a return value like this... although I want all of that in a list as the output

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 just want a way to calculate every combination of those 3 letters. If my list had 4 letters in it then I want every combination of the 4 letters etc. Any ideas? I can't get my head around this problem.

Offline

**regulus6633****Member**- From:: Taulov, Denmark
- Registered: 2006-11-02
- Posts: 1695
- Website

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"}

Offline

**mikerickson****Member**- Registered: 2008-10-26
- Posts: 437

Perhaps

## Applescript:

set inputList to {"a", "b", "c", "d"}

set resultList to {""}

repeat with oneVal in inputList

set resultList to append(resultList, inputList)

end repeat

resultList

on append(someList, anotherList)

set retVal to {}

repeat with aVal in someList

repeat with bVal in anotherList

copy aVal & bVal to end of retVal

end repeat

end repeat

return retVal

end append

-->{"aaaa", "aaab", "aaac", "aaad", "aaba", "aabb", "aabc", "aabd", "aaca", "aacb", "aacc", "aacd", "aada", "aadb", "aadc", "aadd", "abaa", "abab", "abac", "abad", "abba", "abbb", "abbc", "abbd", "abca", "abcb", "abcc", "abcd", "abda", "abdb", "abdc", "abdd", "acaa", "acab", "acac", "acad", "acba", "acbb", "acbc", "acbd", "acca", "accb", "accc", "accd", "acda", "acdb", "acdc", "acdd", "adaa", "adab", "adac", "adad", "adba", "adbb", "adbc", "adbd", "adca", "adcb", "adcc", "adcd", "adda", "addb", "addc", "addd", "baaa", "baab", "baac", "baad", "baba", "babb", "babc", "babd", "baca", "bacb", "bacc", "bacd", "bada", "badb", "badc", "badd", "bbaa", "bbab", "bbac", "bbad", "bbba", "bbbb", "bbbc", "bbbd", "bbca", "bbcb", "bbcc", "bbcd", "bbda", "bbdb", "bbdc", "bbdd", "bcaa", "bcab", "bcac", "bcad", "bcba", "bcbb", "bcbc", "bcbd", "bcca", "bccb", "bccc", "bccd", "bcda", "bcdb", "bcdc", "bcdd", "bdaa", "bdab", "bdac", "bdad", "bdba", "bdbb", "bdbc", "bdbd", "bdca", "bdcb", "bdcc", "bdcd", "bdda", "bddb", "bddc", "bddd", "caaa", "caab", "caac", "caad", "caba", "cabb", "cabc", "cabd", "caca", "cacb", "cacc", "cacd", "cada", "cadb", "cadc", "cadd", "cbaa", "cbab", "cbac", "cbad", "cbba", "cbbb", "cbbc", "cbbd", "cbca", "cbcb", "cbcc", "cbcd", "cbda", "cbdb", "cbdc", "cbdd", "ccaa", "ccab", "ccac", "ccad", "ccba", "ccbb", "ccbc", "ccbd", "ccca", "cccb", "cccc", "cccd", "ccda", "ccdb", "ccdc", "ccdd", "cdaa", "cdab", "cdac", "cdad", "cdba", "cdbb", "cdbc", "cdbd", "cdca", "cdcb", "cdcc", "cdcd", "cdda", "cddb", "cddc", "cddd", "daaa", "daab", "daac", "daad", "daba", "dabb", "dabc", "dabd", "daca", "dacb", "dacc", "dacd", "dada", "dadb", "dadc", "dadd", "dbaa", "dbab", "dbac", "dbad", "dbba", "dbbb", "dbbc", "dbbd", "dbca", "dbcb", "dbcc", "dbcd", "dbda", "dbdb", "dbdc", "dbdd", "dcaa", "dcab", "dcac", "dcad", "dcba", "dcbb", "dcbc", "dcbd", "dcca", "dccb", "dccc", "dccd", "dcda", "dcdb", "dcdc", "dcdd", "ddaa", "ddab", "ddac", "ddad", "ddba", "ddbb", "ddbc", "ddbd", "ddca", "ddcb", "ddcc", "ddcd", "ddda", "dddb", "dddc", "dddd"}

*Last edited by mikerickson (2009-09-06 03:39:25 pm)*

Offline

**daehl****Member**- Registered: 2007-03-09
- Posts: 32

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)*

Offline

**mikerickson****Member**- Registered: 2008-10-26
- Posts: 437

What Regulus was looking for was counting

Given a list of n elements {e0, e1, e2, ...e(n-1)},

list the numbers from 0 to n^(n-1) expressed base n,

substituting the characters e0, e1,...e(n-1) for the normal numeral digits (0,1,2,3,...)

is a restatement of his question.

Also, since lists are not sets, I think that "combination" is an appropriate term.

He's not asking for combination of elements of a set (sets are unordered).

He asked for combinations of elements of a list (lists are ordered).

If you accept that a combination of elements of a list is a list, then its clearly order dependent.

One final point, most often listing all combinations or permutations is unneeded and very very slow. Both grow very fast and get very slow with small values of N.

The most common misuse of listing all combinations is to list all combinations to find the few that meets some condition.

Analysis of the situation is almost always possible and is always faster than listing all of the combinations and searching for those that meet the developer's condition.

"What odd numbers are the sum of unique powers of 2 (9 = 1 + 8 + 8 is not such a number since two of the terms are equal) with the limitation that each term is < 2^16"

List all combinations and select is the wrong way to approach that problem.

*Last edited by mikerickson (2010-02-26 11:35:28 pm)*

Offline

**Nigel Garvey****Moderator**- From:: Warwickshire, England
- Registered: 2002-11-20
- Posts: 5261

daehl wrote:

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.

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.

NG

Offline

**Adam Bell****Administrator**- From:: Nova Scotia, Canada
- Registered: 2005-10-04
- Posts: 4666

@NG;

Certainly blindingly fast, Nigel.

For others who might want to try it, beware the returns the list puts in the comments; particularly the one ending with item l (lower case L), which took me a few minutes to find because it compiles. The entire comment is:

-- Get all permutations of items (l +1) thru r with the current item l

Mac mini running 10.14.6, 2011 27" iMac as display.

Offline

Hello.

The link doesn't work anymore, so I hope someone posts the handlers that was in Nigel Garvey's link.

Here is a quick an dirty solution of my own, to hoover over all combinations of pairs in a set(list/array of elements.

## Applescript:

set n to 4

# A combinatorial loop, that hoovers over all combinations of pairs with two elements in a set/list/array of elements.

repeat with i from 1 to (n - 1)

repeat with j from (i + 1) to n

log "" & i & " x " & j

end repeat

end repeat

(*1 x 2*)

(*1 x 3*)

(*1 x 4*)

(*2 x 3*)

(*2 x 4*)

(*3 x 4*)

*Last edited by McUsrII (2014-10-05 12:50:08 pm)*

**T.B**

p a file peruser, work in progress, but is sane, and lets you copy the file you view to the clipboard. Enter just "p" for help. Slightly better terminal handling, when executing shell commands from within.

Offline

**Nigel Garvey****Moderator**- From:: Warwickshire, England
- Registered: 2002-11-20
- Posts: 5261

McUsrII wrote:

The link doesn't work anymore, so I hope someone posts the handlers that was in Nigel Garvey's link.

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.

NG

Offline

Hello Nigel.

Thank you very much for posting your script. I want to play with it. I prefer lexical permutations as well, where they change the fastest on the right side of it. In Thomas Calculus Version 10 there is a description of a routine for computing the distance between 2 such permutations. The number of interwening permutations + 1. One day, I am going to order that book!

**T.B**

p a file peruser, work in progress, but is sane, and lets you copy the file you view to the clipboard. Enter just "p" for help. Slightly better terminal handling, when executing shell commands from within.

Offline

**Shane Stanley****Member**- From:: Australia
- Registered: 2002-12-07
- Posts: 6436

Nigel Garvey wrote:

No doubt Shane will produce an ASObjC version ere long.

Pass.

Shane Stanley <sstanley@myriad-com.com.au>

www.macosxautomation.com/applescript/apps/

latenightsw.com

Offline

**Nigel Garvey****Moderator**- From:: Warwickshire, England
- Registered: 2002-11-20
- Posts: 5261

Shane Stanley wrote:

Nigel Garvey wrote:No doubt Shane will produce an ASObjC version ere long.

Pass.

Hmmm. Well here's my attempt. Much slower than the vanilla above, but at least it works, which is quite gratifying. **Edits:** Script modified in accordance with Shane's suggestion in the following post and a couple of ideas pinched from Stefan further down the thread.

## Applescript:

use AppleScript version "2.3.1"

use scripting additions

use framework "Foundation"

on allPermutations(theList)

script o

property workArray : missing value -- Formerly 'workList'.

property permutations : {}

property r : (count theList) - 1 -- zero-based index of the rightmost item

property m : r - 1 -- zero-based index of the middle item of the last three

on prmt(l)

-- l is the zero-based 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

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)

-- 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)

end repeat

end if

end prmt

end script

if (o's r < 2) then

-- Special-case lists of less than three items

copy theList to the beginning of o's permutations

if (o's r is 1) then set the end of o's permutations to the reverse of theList

else

-- Otherwise use the recursive handler

set o's workArray to current application's NSMutableArray's arrayWithArray:theList

set o's permutations to current application's NSMutableArray's array()

o's prmt(0)

end if

return o's permutations as list

end allPermutations

*Last edited by Nigel Garvey (2014-10-07 02:03:31 am)*

NG

Offline

**Shane Stanley****Member**- From:: Australia
- Registered: 2002-12-07
- Posts: 6436

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

Shane Stanley <sstanley@myriad-com.com.au>

www.macosxautomation.com/applescript/apps/

latenightsw.com

Offline

**Nigel Garvey****Moderator**- From:: Warwickshire, England
- Registered: 2002-11-20
- Posts: 5261

Thanks, Shane.

Going right up to 9 items on my machine, my vanilla script takes 300 seconds and my ASObjC attempt 115! Your modification only brings this down to 114 seconds, but it's still an obvious improvement and I've edited my post above accordingly.

NG

Offline

**DJ Bazzie Wazzie****Member**- From:: the Netherlands
- Registered: 2004-10-20
- Posts: 2809
- Website

**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)*

Offline

Hello.

Lexical next R- combination:

This is a very nice and useful thread. Some times, it may take a long time to generate a full set of permutations and combinations, then we may create one at a time, to spread the cost. Here is a handler that delivers the next combination. You have to compute the number of combinations up front, so you don't exceed the number of possible combinations, you also have to subtract one combination, since you started with one. For instance, if I start with {1,2}, a pair from the set of {1,2,3,4}, I can only iterate 5 times, since the total number of combinations are 6.

you may of course change the algorithm to start the cycle over again, if you so wish.

## Applescript:

(*

Get next R combination.

Pseudo code from Kenneth. H. Rosen Discrete mathematics and its applications p. 385.

Returns the next set.

a: the former combination

v: the set from where the combinations are from

r: the number of items in the combination.

*)

on next_R_Combination(a, v, r)

set {i, n} to {r, length of v}

if i â‰¥ n then error "next_R_Combination: Error: Subset greater or equal to superset in length."

if r â‰ length of a then error "next_R_Combination: Error: Length of subset not equal to r."

try

repeat while (item i of a) = n - r + i

set i to i - 1

end repeat

on error

error "next_R_Combination: Error: Passed over the last combination"

end try

set item i of a to ((item i of a) + 1)

repeat with j from (i + 1) to r

set item j of a to (item i of a) + j - i

end repeat

return a

end next_R_Combination

(*

# driver for next_R_Combination

set m to next_R_Combination({1, 2, 5, 6}, {1, 2, 3, 4, 5, 6}, 4)

--> {1, 3, 4, 5}

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

*)

Edited, removed superfluous assignment in the driver/test of the algorithm.

Added some clarity to the description of the handler.

*Last edited by McUsrII (2014-10-06 12:49:29 pm)*

**T.B**

p a file peruser, work in progress, but is sane, and lets you copy the file you view to the clipboard. Enter just "p" for help. Slightly better terminal handling, when executing shell commands from within.

Offline

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

*)

**T.B**

p a file peruser, work in progress, but is sane, and lets you copy the file you view to the clipboard. Enter just "p" for help. Slightly better terminal handling, when executing shell commands from within.

Offline

**Nigel Garvey****Moderator**- From:: Warwickshire, England
- Registered: 2002-11-20
- Posts: 5261

DJ Bazzie Wazzie wrote:

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

Hi DJ.

I've just added a comment about that script to the end of that thread.

Otherwise, I'm not quite sure what you're saying about it. Are you asking for an AppleScriptObjC version?**Edit:** Here is one. You call the 'permute' handler with just the original list. It's not as fast as the script in post #13.**Further edits:** Another script improvement from Shane and two from Stefan.

## Applescript:

use AppleScript version "2.3.1"

use scripting additions

use framework "Foundation"

property permutations : missing value

on permute(theList)

set theArray to current application's NSMutableArray's arrayWithArray:theList

set permutations to current application's NSMutableArray's array()

prmt(theArray, 0, (count theList) - 1)

return my permutations as list

end permute

on prmt(theArray, theStart, theEnd)

if (theStart = theEnd) then

permutations's addObject:theArray

else

repeat with x from theStart to theEnd

set theCopy to theArray's mutableCopy()

--swap

if (x > theStart) then (theCopy's exchangeObjectAtIndex:theStart withObjectAtIndex:x)

prmt(theCopy, theStart + 1, theEnd)

end repeat

end if

end prmt

*Last edited by Nigel Garvey (2014-10-07 02:08:07 am)*

NG

Offline

**Shane Stanley****Member**- From:: Australia
- Registered: 2002-12-07
- Posts: 6436

Nigel Garvey wrote:

Going right up to 9 items on my machine, my vanilla script takes 300 seconds and my ASObjC attempt 115!

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.

Shane Stanley <sstanley@myriad-com.com.au>

www.macosxautomation.com/applescript/apps/

latenightsw.com

Offline

**Shane Stanley****Member**- From:: Australia
- Registered: 2002-12-07
- Posts: 6436

DJ Bazzie Wazzie wrote:

The AppleScriptObjC version completely depends on AppleEvents but has no data handling on it's own.

Perhaps I misunderstand what you're getting at, but AppleScriptObjC doesn't involve any Apple events.

It so happens that for the first time I see that AppleScriptObjC comes close to OSAX in performance.

That is interesting. If you were anyone else, I'd tell you to check your code

www.macosxautomation.com/applescript/apps/

latenightsw.com

Offline

**Shane Stanley****Member**- From:: Australia
- Registered: 2002-12-07
- Posts: 6436

Nigel Garvey wrote:

## Applescript:

set theCopy to (current application's NSMutableArray's arrayWithArray:theArray) -- theArray's |copy|() apparently produces an immutable array.

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.

www.macosxautomation.com/applescript/apps/

latenightsw.com

Offline

Hi,

here a Objective-C version using the Heap's algorithm (300 ms for 9 elements)

## Applescript:

@import Foundation

NSMutableArray *inputArray, *outputArray;

void heapPermute(n) {

if (n == 1) {

[outputArray addObject:[inputArray copy]];

} else {

for (int i = 0; i < n; i++) {

heapPermute(n-1);

if (n % 2 == 1) {

[inputArray exchangeObjectAtIndex:0 withObjectAtIndex:n-1];

} else {

[inputArray exchangeObjectAtIndex:i withObjectAtIndex:n-1];

}

}

}

}

int main (int argc, const char * argv[]) {

@autoreleasepool {

outputArray = [NSMutableArray array];

inputArray = [NSMutableArray arrayWithObjects:@"black", @"dark brown", @"beige", @"blue", @"yellow", @"magenta", @"green", @"red", @"gray", nil];

heapPermute([inputArray count])

}

return 0;

}

and just for fun a Swift version (not measured)

## Applescript:

var inputArray = ["black", "dark brown", "beige", "blue", "yellow"]

var outputArray = [Array<String>]()

func swap(i : Int, j : Int) {

let temp = inputArray[i]

inputArray[i] = inputArray[j]

inputArray[j] = temp

}

func heapPermute(n : Int) {

if n == 1 {

outputArray.append(inputArray)

}

else {

for i in 0..<n {

heapPermute(n-1)

if (n % 2 == 1) {

swap(0, n-1)

} else {

swap(i, n-1)

}

}

}

}

heapPermute(inputArray.count)

*Last edited by StefanK (2014-10-06 04:45:35 pm)*

regards

Stefan

Offline

**Nigel Garvey****Moderator**- From:: Warwickshire, England
- Registered: 2002-11-20
- Posts: 5261

Shane Stanley wrote:

Nigel Garvey wrote:## Applescript:

set theCopy to (current application's NSMutableArray's arrayWithArray:theArray) -- theArray's |copy|() apparently produces an immutable array.

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?

NG

Offline

**Nigel Garvey****Moderator**- From:: Warwickshire, England
- Registered: 2002-11-20
- Posts: 5261

StefanK wrote:

â€¦ (300 ms for 9 elements)

Well that's certainly the fastest so far! Is it usable from AppleScript?

NG

Offline