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!):
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"}}
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)
