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.
(*
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.
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”.
(*
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
*)
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.
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
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?
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:
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
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:
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.
… I understand, but you make me uncertain about it I will take a look into that code tomorrow.