Wednesday, December 7, 2022

Announcement

MacScripeter.net will transition to a new Discourse server soon. Watch this space for the date and time of the transition. Please expect the site to experience periods of outage during this transition. See this and this for more details.

#51 2014-10-09 05:45:11 pm

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

Re: get all combinations

Nigel Garvey wrote:

By means of concatenation, this vanilla version of my script prebuilds a list of the required length to hold the permutations. When used as a Library in exactly the same way as the ASObjC version in post #13, it executes in a mere 5 seconds or so as opposed to the ASObjC version's 134 seconds! However, with both versions, it then takes nearly two and a half minutes to do anything with the result, such as setting a variable to it or getting its class!


I'm not sure what you're timing, but yes, most stuff would be much quicker if we didn't have to await results wink


Shane Stanley <sstanley@myriad-com.com.au>
www.macosxautomation.com/applescript/apps/
latenightsw.com

Offline

 

#52 2014-10-10 06:42:52 am

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

Re: get all combinations

Shane Stanley wrote:

I'm not sure what you're timing …


It's the time taken to execute the permutations code with a nine-item input list versus the time taken to execute the code and set a variable to the result. The difference is about two to two-and-a-half minutes! The same's true for getting information from the result, such as its class or the value of one of its items.

Here's the timing script I've been using in AppleScript Editor. Only the timing result appears in the Result pane, so the time it would take to decompile all the permutations for display isn't a factor:

Applescript:

use permuter : script "Permuter 4" -- The vanilla script in post #49.
use scripting additions

----------
-- "Timer.scpt" is a script on my own computer. The current script won't work without it (or a similar one).
tell me to set timer to (load script file ((path to scripts folder from user domain as text) & "Libraries:Timer.scpt"))
tell timer to StartTimer()
----------
permuter's allPermutations({1, 2, 3, 4, 5, 6, 7, 8, 9}) -- Timed code.
----------
tell timer to set t to readTimer()
----------
(*
Sample results this morning vary between 4.964 and 6.342 seconds.
But changing the timed code to:
set l to permuter's allPermutations({1, 2, 3, 4, 5, 6, 7, 8, 9})
--> 120.436 to 132.929 seconds.
*)

The situation's similar when timing the ASObjC version, but with longer times:

Applescript:

use permuter : script "Permuter 3" -- The ASObjC script in post #13.
use scripting additions

----------
-- "Timer.scpt" is a script on my own computer. The current script won't work without it (or a similar one).
tell me to set timer to (load script file ((path to scripts folder from user domain as text) & "Libraries:Timer.scpt"))
tell timer to StartTimer()
----------
permuter's allPermutations({1, 2, 3, 4, 5, 6, 7, 8, 9}) -- Timed code.
----------
tell timer to set t to readTimer()
----------
(*
Sample results this morning vary between 131.031 and 137.428 seconds.
But changing the timed code to:
set l to permuter's allPermutations({1, 2, 3, 4, 5, 6, 7, 8, 9})
--> 257.602 to 260.286 seconds.
*)


NG

Online

 

#53 2014-10-10 04:53:22 pm

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

Re: get all combinations

Interesting.

Let me add a few comments about ASObjC and this thread. One of the reasons I was initially reluctant to bother with an ASObjC version is that I didn't think it would offer any advantage. And ultimately it didn't, except by bending the test in its favor with very large lists -- so large, they are probably practically unusable in AS.

Where ASObjC is likely to offer real speed gains, I think, is in cases where it can replace algorithms. Things like using a sort method, or using classes like sets to make lists unique. Although this might look a bit like cheating, and at times be downright dull, I think it's very much in the spirit of AppleScript and things like the whose clause: real speed gains are generally made by pushing the work out to be done somewhere else. And while we're all happy to see clever algorithms implemented in Nigel's hands, less code means less chance for bugs.


Shane Stanley <sstanley@myriad-com.com.au>
www.macosxautomation.com/applescript/apps/
latenightsw.com

Offline

 

#54 2014-10-11 12:49:57 pm

McUsrII
Member
Registered: 2012-11-21
Posts: 3046
Website

Re: get all combinations

Hello.

I felt that an r-permutation with repeats was missing here, that is permutations with r elements, from a set of n elements, with repeating elements.

There isn't much to say about the implementation, other than that it works like an odometer basically. If we make permutations with a size of r elements, over a set of n elements, with repeats, then we must generate n^r combinations.

I have also left out zero as a valid element, and I intend to use this with daehls delist handler, for translating back and forth.

Applescript:

set thePerms to {}

r_permute_reps(3, 5, thePerms)
listprint(thePerms)
(*
"{1, 1}
{1, 2}
{1, 3}
{1, 4}
{1, 5}
{2, 1}
{2, 2}
{2, 3}
{2, 4}
{2, 5}
{3, 1}
{3, 2}
{3, 3}
{3, 4}
{3, 5}
{4, 1}
{4, 2}
{4, 3}
{4, 4}
{4, 5}
{5, 1}
{5, 2}
{5, 3}
{5, 4}
{5, 5}"
*)

on r_permute_reps(n, r, perm_list)
   
   set oldperm to {}
   repeat with i from 1 to r
       -- initialize oldperm
       set end of oldperm to 1
   end repeat
   copy oldperm to end of perm_list
   repeat with i from 1 to (n ^ r - 1)
       if ((item r) of oldperm < n) then
           set (item r) of oldperm to ((item r) of oldperm) + 1
       else
           set (item r) of oldperm to 1
           repeat with j from (r - 1) to 1 by -1
               if item j of oldperm < n then
                   set item j of oldperm to (item j of oldperm) + 1
                   exit repeat
               else
                   set item j of oldperm to 1
               end if
           end repeat
       end if
       copy oldperm to end of perm_list
       
   end repeat
end r_permute_reps

on listprint(theL)
   try
       text 0 of theL
   on error e
       set ofs to offset of "{" in e
       set tmp to text (ofs + 1) thru -3 of e
       tell (a reference to text item delimiters)
           set astid to contents of it
           set contents of it to "}, "
           set newl to text items of tmp
           set contents of it to "}" & return
           set newt to newl as text
           set contents of it to astid
       end tell
       return newt
   end try
end listprint

Edit

Added some code that was forgotten so it works for r's >2. hmm

Last edited by McUsrII (2014-10-11 12:50:45 pm)

Offline

 

#55 2015-05-07 05:05:28 am

McUsrII
Member
Registered: 2012-11-21
Posts: 3046
Website

Re: get all combinations

Hello.

Here is yet another handler, this time one that returns the powerset of a set. A power set, is the combination of all sets that can be made from the original set.

I have used handlers that I have posted earlier in this thread, and included them here, so it works as it is is posted.

Applescript:


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 combination(combinations, r, n)
   # print the first r combination
   set s to {}
   repeat with i from 1 to r
       set end of s to i
   end repeat
   copy s to end of combinations
   
   repeat with i from 2 to my c(n, r)
       set m to r
       set max_val to n
       
       repeat while (((item m) of s) = max_val)
           set m to m - 1
           set max_val to max_val - 1
       end repeat
       # increment the above rightmost element
       set item m of s to (item m of s) + 1
       # all others are the successors:
       
       repeat with j from (m + 1) to r
           set item j of s to (item (j - 1) of s) + 1
       end repeat
       copy s to end of combinations
   end repeat
end combination

on createPowerSet from origSet
   -- assumes the set is made up of consecutive integers, starting at 1.
   -- i.e. {1,2,3} is a valid set, {2,5,6} is not. You may make your own mapping of sorts, of course.
   -- Number of sets in the powerset is 2 ^(length of origset)
   set powSet to {origSet}
   set origLen to (length of origSet)
   repeat with i from (origLen - 1) to 1 by -1
       combination(powSet, i, origLen)
   end repeat
   set end of powSet to {}
   return powSet
end createPowerSet


createPowerSet from {1, 2, 3}
-- {{1, 2, 3}, {1, 2}, {1, 3}, {2, 3}, {1}, {2}, {3}, {}}

Last edited by McUsrII (2015-05-07 05:07:24 am)


Filed under: combinations, powerset

Offline

 

#56 2018-08-21 08:42:46 am

technomorph
Member
Registered: 2017-12-14
Posts: 304

Re: get all combinations

daehl wrote:


Applescript:


           repeat while (i > 1 and c's item i ≥ n - k + 1 + i)
               
   if 0 < k and k ≤ n then
       



could you decode the above characters?

≥
≤

thanks

Offline

 

#57 2018-08-21 10:23:39 am

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

Re: get all combinations

Sorry. They're due to a change in MacScripter's BBS software a year or two ago.

What gets the same results as daehl is to change ≥ to (greater than or equal to) and ≤ to (less than or equal to).


NG

Online

 

Board footer

Powered by FluxBB

RSS (new topics) RSS (active topics)