Thursday, October 6, 2022

You are not logged in.

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

Nigel Garvey wrote:

So in fact the initial manifestation of 'theArray' needn't be mutable.

That's right.

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.

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: 6793

Nigel Garvey wrote:

Is it usable from AppleScript?

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/ap … xtras.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.

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

www.macosxautomation.com/applescript/apps/

latenightsw.com

Offline

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

Shane Stanley wrote:

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.

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.

Shane Stanley wrote:

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

... I understand, but you make me uncertain about it I will take a look into that code tomorrow.

Offline

Nigel Garvey wrote:

Is it usable from AppleScript?

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

## Applescript:

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

regards

Stefan

Offline

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

StefanK wrote:

## Applescript:

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!

NG

Offline

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

Shane Stanley wrote:

The best answer I can give is â€¦

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?

NG

Offline

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

Nigel Garvey wrote:

your definitive beginners' book about ASObjC, of which I gather there's soon to be a second edition covering the changes in Yosemite?

Yes, now that AppleScriptObjC is finally going to live up to my book's title , a second edition is in the pipeline.

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

www.macosxautomation.com/applescript/apps/

latenightsw.com

Offline

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

## 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 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.

*Last edited by McUsrII (2014-10-07 06:47:51 am)*

**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 wrote:

I think your

addObject:parameter should beinputArray's |copy|().

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

regards

Stefan

Offline

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

StefanK wrote:

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.

Offline

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

StefanK wrote:

Nigel Garvey wrote:I think your

addObject:parameter should beinputArray's |copy|().

thanks, but it's not considerable faster.

Hi Stefan.

No. It's probably a little slower. I was thinking more in terms of producing right results.

NG

Offline

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

DJ Bazzie Wazzie wrote:

Shane Stanley wrote:DJ Bazzie Wazzie wrote: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

... I understand, but you make me uncertain about it I will take a look into that code tomorrow.

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:

//

// main.c

// permutation

//

// Created by Bastiaan on 07-10-14.

// Copyright (c) 2014 All rights reserved.

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

void printPermutations(int **allPermutations, int index, int len);

void permute(int * theList, int begin, int end, int **allPermutations, int*allPermutationLen);

void swapItems (int *itemA, int *itemB);

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

{

// variables needed to time the elapsed time

clock_t startTime;

clock_t endTime;

clock_t time_spent;

int listSize = 11; //change this value to size of list to permutate

int *theList = malloc(sizeof(int) *listSize);

int **allPermutations;

int allPermutationSize = 1; //how big will the list be

int allPermutationLen = 0; //wat what current position are we

// calulate the size needed to store all permutations

for (int i = 1;i < listSize +1; i++)

allPermutationSize = allPermutationSize * i;

// allocate the memory needed to store linear all pointers

// to every possible permutation. This will avoid the flooding

// of reallocations otherwise is needed.

allPermutations = malloc(sizeof(int *) * allPermutationSize);

// create a list of integers starting from 1 to ...

for (int i =0;i<listSize;i++)

theList[i] = i;

// get start time

startTime = clock();

//start permutation

permute(theList, 0, listSize -1, allPermutations, &allPermutationLen);

// get stop time

endTime = clock();

// subtract the start to finish time to get the elapsed time in milliseconds

time_spent = (endTime - startTime) / (CLOCKS_PER_SEC / 1000);

//print to stdout the eleapsed tim in milliseconds

printf("Execution took %li ms\n", time_spent);

//print number of permutations

printf("Number of permutations are %i items\n", allPermutationSize);

//print first and last permutation just for checking

printPermutations(allPermutations, 0, listSize);

printPermutations(allPermutations, allPermutationSize -1, listSize);

// actually we should free memory here, but we reached end of program

return 0;

}

void printPermutations(int **allPermutations, int index, int len)

{

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

printf("%i", allPermutations[index][i]);

if (i == (len -1)){

printf("\n");

} else {

printf(", ");

}

}

}

void permute(int * theList, int begin, int end, int **allPermutations, int*allPermutationLen)

{

// check if we're at the last item in the list

if (begin == end){

// We're at the last item in the list, it reached

// reached the bottom level in the recursion. Copy

// the current state of theList to allPermutations

// allocate a new array

int * item = malloc(sizeof(int) * (end+1));

// copy each item of the current state of theList to theItem

for (int i =0; i < end+1; i++) {

item[i] = theList[i];

}

// save a pointer to 'item' and save it in the

// allPermutation array and increment insertion

// point allPermutationLen by 1

allPermutations[(*allPermutationLen)++] = item;

} else {

//begin a loop to loop through all remaining items

for (int i = begin;i < end+1;i++){

//only swap when needed

if (i != begin)

// swap item with first remaining item

swapItems((theList +i), (theList + begin));

// call me again but this time start with the next item in theList

permute(theList, begin +1, end, allPermutations, allPermutationLen);

// only swap back when swapped before

if (i != begin)

// swap back, the next loop has to begin with

// theList in the same order as we started the function

swapItems((theList +i), (theList + begin));

}

}

}

void swapItems (int *itemA, int *itemB)

{

// Swap: create a temporary container,

// copy value of itemA to itemX, copy value itemB to itemA (overwrite) and

// then copy tmp to y.

int itemX;

itemX = *itemA;

*itemA = *itemB;

*itemB = itemX;

}

Offline

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

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:

## Applescript:

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

www.macosxautomation.com/applescript/apps/

latenightsw.com

Offline

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

DJ Bazzie Wazzie wrote:

So the delay in my OSAX is really handling and copying AppleEvent descriptors.

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.

www.macosxautomation.com/applescript/apps/

latenightsw.com

Offline

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

Shane Stanley wrote:

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:

Hi Shane.

Your assumption's party right. As you probably noticed, my first ASObjC script (post #13) is just a revamp of my right-to-left vanilla script from post #10, with ObjC arrays and methods used instead of vanilla where there are more than two items.

In the vanilla scripts, the script-object-within-a-handler idea offers three advantages (to my way of thinking):

1. The script object's properties can be "referenced" to allow faster access to the vanilla list items.

2. The recursive part of the only-partially recursive process can be contained within the main handler.

3. The lists and the precalculated r and m values can be held in local properties instead of having to be passed or recalculated with each recursion or held in globals or global properties outside the main handler.

Point 1, as you say, doesn't apply with the ObjC arrays. Point 2 is a largely a matter of my own personal preference. Point 3 is connected with point 2, but is also relevant with regard to the amount of work the script has to do. Your rewrite passes two extra parameters AND recalculates r and m on every call to the recursive handler. I'd therefore expect it to be a little *slower* than my script. And it is, on my machine. With nine items, it's taking about six seconds longer than mine this morning. But mine's taking a fair bit longer than it did yesterday, so the difference between the scripts' times may actually be less under optimal conditions.

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.

Now that's interesting! But the difference is far less dramatic for me. 117 seconds as opposed to 134 (this morning). Still, that's a lot more than I'd have expected until you mentioned it.

NG

Offline

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

Yes, I found it a bit slower here too, although I got a bit excited when I accidentally left a number off the initial list

That coercion time is the killer. I found when I wrote ASObjC Runner that with even modest lists of lists, virtually all the time was taken converting AS stuff to Cocoa and vice-versa; the work performed was almost irrelevant most of the time. One of the advantages of having ASObjC everywhere is that it makes it easier to do the conversions only when you need to.

www.macosxautomation.com/applescript/apps/

latenightsw.com

Offline

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

Shane Stanley wrote:

DJ Bazzie Wazzie wrote:So the delay in my OSAX is really handling and copying AppleEvent descriptors.

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.

Exactly! Nigel's code took 45 seconds on my MBP when an AppleScript list is returned but when I return a pointer to the NSMutableArray it took only 40 seconds. That means that AppleScriptObjC bridge will take up to 5 seconds to coerce to a NSMutableArray containing 362,880 items into an AppleScript list. That fits right with my OSAX "problem" because when thinking about it, the AEPutParamDesc does an extra copy of the object meaning it will take two times 5 seconds (and probably some more copying when the event is handled by the event manager).

Offline

It's getting nicer and nicer.

But â€¦ if you make a list of 362,880, I have to assume that you are going to use that list for something other than just generating it, and then, those 10 seconds, won't take up that much time proportionally. You can for all I know, execute an Osascript in the background, from a do shell script for all I know.

I have another approach, I generate permutations, or combinations on the fly, paying a penalty with each invocation, I live well with that, at least until I have timed it, because I have a practical need for testing if vectors in matrix are orthogonal to each other, by testing them accordingly to generated combinations. If a test fails, then I must start over from scratch. So I pay a penalty in total time, but saves some time per invocation, and some memory too! I have no idea how I would create a list with 362880 items in Applescript however. Have the boundaries changed?

There are however a lot of things lists with permutations and combinations that are generated up front can be used for. Today I have understood how mikerickson's algorithm for generating permutations with repeats works, it is pretty clever I think.

This is really a great thread.

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

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

McUsrII wrote:

I have no idea how I would create a list with 362880 items in Applescript however. Have the boundaries changed?

AppleScript allows lists up to 2^31 items, well at least in theory. Because the maximum allowed index is the maximum value of a signed 32-bit integer and negative indexes are not allowed. To create a list with 362880 items, there is no problem you just have to wait 20+ seconds.

*Last edited by DJ Bazzie Wazzie (2014-10-08 08:26:52 am)*

Offline

Hello DJ.

Thanks for enlightening me, I was dead sure anything above 2^14 was futile.

20 seconds isn't a long time, except for when in front of a computer!

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

For those interested, here is a generator of r-combinations. There is nothing wrong with Daehls, I just wanted something simpler to understand as the problem intrigued me, so this is probably slower. I found the pseudo code in a buggy! pdf document somwhere. (Daehls delist handler is something that seems to be a great way to translate items into indicies IMO.)

## Applescript:

set comboList to {}

combination(comboList, 3, 6)

listprint(comboList)

(*

"{1, 2, 3}

{1, 2, 4}

{1, 2, 5}

{1, 2, 6}

{1, 3, 4}

{1, 3, 5}

{1, 3, 6}

{1, 4, 5}

{1, 4, 6}

{1, 5, 6}

{2, 3, 4}

{2, 3, 5}

{2, 3, 6}

{2, 4, 5}

{2, 4, 6}

{2, 5, 6}

{3, 4, 5}

{3, 4, 6}

{3, 5, 6}

{4, 5, 6}"

*)

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

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

**Edit**

Made a "fancier" listprint handler.

*Last edited by McUsrII (2014-10-08 02:36:58 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.

I have made a handler for generating combinations with repetitions, for completion, since we then have all kinds of handlers here. You'll have to allow for every element being chosen as many times as there are rooms in your subset.

## Applescript:

set comboList to {}

set donuts to {"iced", "jam", "plain", "something completely different"}

set chosen to {0, 0, 0, 0}

# the number of items in the list chosen, must coincide with the n_chosen parameter.

choose(comboList, chosen, 1, 4, 1, 3)

--> 15 (combinations

listprint(comboList)

(*

"{\"iced\", \"iced\", \"iced\", \"iced\"}

{\"iced\", \"iced\", \"iced\", \"jam\"}

{\"iced\", \"iced\", \"iced\", \"plain\"}

{\"iced\", \"iced\", \"jam\", \"jam\"}

{\"iced\", \"iced\", \"jam\", \"plain\"}

{\"iced\", \"iced\", \"plain\", \"plain\"}

{\"iced\", \"jam\", \"jam\", \"jam\"}

{\"iced\", \"jam\", \"jam\", \"plain\"}

{\"iced\", \"jam\", \"plain\", \"plain\"}

{\"iced\", \"plain\", \"plain\", \"plain\"}

{\"jam\", \"jam\", \"jam\", \"jam\"}

{\"jam\", \"jam\", \"jam\", \"plain\"}

{\"jam\", \"jam\", \"plain\", \"plain\"}

{\"jam\", \"plain\", \"plain\", \"plain\"}

{\"plain\", \"plain\", \"plain\", \"plain\"}"

*)

(*

The calculation for the number of combinations with repetitions are:

C( maxtypes+n_chosen-1,n_chosen) or C(n+r-1,r) with other variable names.

*)

log C(3 + 4 - 1, 4)

--> 15

on choose(combinations, got, n_chosen, len, atw, maxtypes)

global donuts

set tcount to 0

if n_chosen = (len + 1) then

# log "n_chosen = len "

if got = 0 then return 1

set lineout to {}

repeat with i from 1 to len

set end of lineout to item (item i of got) of donuts

end repeat

copy lineout to end of combinations

return 1

end if

repeat with i from atw to maxtypes

if (got â‰ 0) then

set item n_chosen of got to i

set tcount to tcount + choose(combinations, got, (n_chosen + 1), len, i, maxtypes)

end if

end repeat

return tcount

end choose

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

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

**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: 5570

Here's an interesting one.

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!

## Applescript:

on allPermutations(theList)

script o

property workList : missing value

property permutations : {}

property r : count theList -- index of the rightmost item of workList.

property m : r - 1 -- index of the middle item of the last three of workList.

property p : 1 -- index into the permutations list.

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 is 3) then

-- These six permutations are hard-coded to reduce low-level recursion

copy my workList to item p 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 item (p + 1) of my permutations

set item l of my workList to v2

set item r of my workList to v1

copy my workList to item (p + 2) of my permutations

set item m of my workList to v1

set item r of my workList to v3

copy my workList to item (p + 3) of my permutations

set item l of my workList to v3

set item r of my workList to v2

copy my workList to item (p + 4) of my permutations

set item m of my workList to v2

set item r of my workList to v1

copy my workList to item (p + 5) of my permutations

set my p to p + 6

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 theList

else

-- Otherwise use the recursive handler

copy theList to o's workList

-- Prebuild a list of the required length (factorial of theList's length) to hold the permutations.

set mv to missing value

set mvList to {mv, mv, mv, mv, mv, mv} -- Minimum length is 6 with a 3-item input list.

set mvList2 to mvList

repeat with i from 3 to (o's r) - 1

repeat i times

set mvList2 to mvList2 & mvList

end repeat

set mvList to mvList2

end repeat

set o's permutations to mvList

o's prmt(1)

end if

return o's permutations

end allPermutations

NG

Offline

Hello.

Your handlers are as eminent as well always. I guess you just stay with AsobjC, when time is precarious enough.

I figure that the data, the permuations are used for, are maybe less demanding with regards to copying them in, a little at a time from vanilla Applescript.

It is very comforting to know that such handlers exists, DJ's handler from that other thread is also a nice one, for practical purposes. This is such a great and fun thread!

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