Perhaps I misunderstand what you’re getting at, but AppleScriptObjC doesn’t involve any Apple events.
That is interesting. If you were anyone else, I’d tell you to check your code 
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.
Hi,
here a Objective-C version using the Heap’s algorithm (300 ms for 9 elements)
@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)
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)
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?
Well that’s certainly the fastest so far! Is it usable from AppleScript?
That’s right.
The best answer I can give is “possibly”. The thing with classes like array is that they are implemented as what are known as “class clusters”. In other words, there are a whole lot of subclasses, optimized for different situations, and there is no guarantee which you get – only that they respond to the same methods. As an example, the subclass used for an array of a dozen items will be quite different to the one used for an array of thousands of items.
And the implementations can (and do) change over time, sometimes dramatically – they are strongly regarded as implementation details, not to be relied upon.
I’ve seen suggestions that mutableCopy differs from copy only in that it marks the new entity as potentially mutable, which would presumably mean negligible impact.
The preference for immutable flavors boils down to safety most times, I think – you can’t accidentally change them.
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/apps/ASObjCExtras.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.
My mistake, what I meant was the ocid class which I referred to as the C data type named AppleEvent, not as in AppleEvents in sending and receiving events from one process to another.
… I understand, but you make me uncertain about it I will take a look into that code tomorrow.
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
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
Hi Stefan.
I think your addObject: parameter should be inputArray’s |copy|().
With that sorted out, my script in post #13 is still the fastest ASObjC offering here so far, but this is just because it uses Sedgewick’s idea of replacing the three lowest levels of recursion with one written-out piece of code. It’s about to get a little faster as I’ve noted your use of the array() and addObject: methods, which are a definite improvement over what I was using before. Thanks!
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? :rolleyes:
Yes, now that AppleScriptObjC is finally going to live up to my book’s title ;), a second edition is in the pipeline.
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).
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.
thanks, but it’s not considerable faster.
Meanwhile I measured the Swift version, the result is very surprising.
Based on the Heap’s algorithm with 9 items (362880 permutations)
Objective-C : 300 ms
Swift with Foundation arrays : 1,3 s
Swift with native Swift arrays : 18 s
Since we’re involving other programming languages, native C does it in 15ms, for 9 items.
Hi Stefan.
No. It’s probably a little slower. I was thinking more in terms of producing right results. 
Got it.
When implementing my code as native C without using any AEDesc and AEDescList types (and their associate functions) but simple array of int values, it’s done in 15 ms on an old MacBook Pro from 2011. So the delay in my OSAX is really handling and copying AppleEvent descriptors. But I was cheating, I only swapped and printed them (and ignoring the results). In my second attempt I have created an int ** to lookup performance differences.
The results were that it took 30ms to actually find every permutation for a list of 9 items and copy them to an listed list of arrays (or array of pointer pointers). in that case someone could really do something with the results for later processing. I also tried to find the permutations of a list of 11 integers. It comes back with a list containing almost 40 million permutations (39,916,800 to be excactly) just under 4 seconds.
Anyway, if anyone is interested in the code:
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:
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
That makes sense. If you modify Nigel’s script to remove the coercion of the final array to an AS list, the script runs in less than half the time. Put another way, the single act of coercing the array of arrays to an AS list accounts for more than 50% of the running time. And assuming that you can’t do that coercion to a descriptor at your end any quicker, that means the best overall result you can achieve is roughly half the time of the ASObjC version, even if you build the array in a nanosecond.
The other question is what someone is going to do with such a list. I mean, rather than say repeating through a long list in AS, it may be quicker to leave the main list as an array, and just coerce each item as you use it. That’s just moving the job elsewhere in code, but it may save time by skipping a large AS repeat loop.