How to do combinations no repeat with either Numbers or Apple script

Hello

You may try the AppleScript script listed below. It will put the result in the clipboard.

E.g.,

70 = 70 91 = 91 161 = 70 + 91 184 = 184 196 = 196 217 = 217 254 = 70 + 184 266 = 70 + 196 275 = 91 + 184 287 = 70 + 217 . . . 2450 = 70 + 184 + 196 + 330 + 1670 2464 = 70 + 330 + 394 + 1670 2465 = 184 + 217 + 394 + 1670 2471 = 70 + 184 + 217 + 330 + 1670 2477 = 196 + 217 + 394 + 1670 2483 = 70 + 196 + 217 + 330 + 1670 2485 = 91 + 330 + 394 + 1670 2492 = 91 + 184 + 217 + 330 + 1670 2504 = 91 + 196 + 217 + 330 + 1670 2505 = 835 + 1670

Good luck,

H

_main() on _main() script o property |SEEDS| : {70, 91, 184, 196, 217, 330, 394, 835, 1670} property |MAX| : 2505 property pp : {} property qq : {} property rr : {} on cmp(x, y) (* comparator for msort handler *) x's item 1 > y's item 1 end cmp repeat with i from 1 to count my |SEEDS| set pp to combination(|SEEDS|, i) repeat with p in my pp set p to p's contents set q to sum(p) if q > |MAX| or q is in my qq then -- skip this combination else set my qq's end to q set my rr's end to {q, p} end if end repeat end repeat msort(rr, cmp) --return {count rr, rr} -- for test repeat with r in (a reference to my rr) set r's contents to "" & r's item 1 & " = " & _join(r's item 2, " + ") -- N = A + B + ... --set r's contents to _join(r's item 2, " + ") & " = " & r's item 1 -- A + B + ... = N end repeat set r to _join(rr, linefeed) & linefeed set the clipboard to r return r end script tell o to run end _main on combination(xx, n) -- v1.02f3 (* list xx: list of items int n: number of items in each combination return list: list of combinations *) script o property aa : xx's contents property bb : {} property cc : {} property dd : {} if n = 0 then return {} if n = 1 then repeat with a in my aa set a to a's contents if {{a}} is not in my cc then set end of my cc to {a} end repeat return my cc's contents end if repeat (count my aa) - n + 1 times set a to my aa's item 1 set aa to my aa's rest if {a} is in my dd then -- prune this branch else set bb to combination(my aa, n - 1) repeat with b in my bb set end of my cc to {a} & b's contents end repeat set end of my dd to a -- add to prune list end if end repeat return my cc's contents end script tell o to run end combination on sum(xx) (* list xx : list of numbers return number : sum of numbers in xx *) set result to 0 repeat with x in xx result + x end repeat result end sum on msort(aa, cmp_) -- v1.2f2 (* Basic recursive merge sort handler having list sorted in place *) (* list aa : list to be sorted in place handler cmp_ : comparator * cmp_(x, y) must return true iff list element x and y are out of order. *) script o property parent : {} -- limit closure to minimum property xx : aa -- to be sorted in place property xxl : count my xx property yy : {} property cmp : cmp_ on merge(p, q, r) (* property xx: source list integer p, q, r : absolute indices to specify range to be merged such that xx's items p thru r is the target range, xx's items p thru (q-1) is the first sublist, xx's items q thru r is the second sublist. (p < q <= r) *) local i, j, k, xp, xr, yi, yj, ix, jx if r - p = 1 then set xp to my xx's item p set xr to my xx's item r if my cmp(xp, xr) then set my xx's item p to xr set my xx's item r to xp end if return -- exit else if p < q - 1 then merge(p, (p + q) div 2, q - 1) merge(q, (q + r + 1) div 2, r) end if (* At this point, sublits xx[p, q-1] and xx[q, r] have been already sorted (p < q <= r) *) if my cmp(my xx's item (q - 1), my xx's item q) then else -- xx[p, q-1] & xx[q, r] are already sorted return end if set yy to my xx's items p thru r -- working copy for comparison set ix to q - p set jx to r - p + 1 set i to 1 set j to q - p + 1 set k to p set yi to my yy's item i set yj to my yy's item j repeat if my cmp(yi, yj) then set my xx's item k to yj set j to j + 1 set k to k + 1 if j > jx then set my xx's item k to yi set i to i + 1 set k to k + 1 repeat until k > r set my xx's item k to my yy's item i set i to i + 1 set k to k + 1 end repeat return end if set yj to my yy's item j else set my xx's item k to yi set i to i + 1 set k to k + 1 if i > ix then set my xx's item k to yj set j to j + 1 set k to k + 1 repeat until k > r set my xx's item k to my yy's item j set j to j + 1 set k to k + 1 end repeat return end if set yi to my yy's item i end if end repeat end merge on _cmp_(x, y) (* primary comparator *) return x > y end _cmp_ if xxl ≤ 1 then return if cmp_ = {} then set my cmp to _cmp_ -- comparator fallback my merge(1, (xxl + 2) div 2, xxl) end script tell o to run end msort on _join(tt, d) (* list tt : source list string d : separator return string : tt joined with d *) local astid0, t try set {astid0, AppleScript's text item delimiters} to {AppleScript's text item delimiters, {} & d} set t to "" & tt set AppleScript's text item delimiters to astid0 on error errs number errn set AppleScript's text item delimiters to astid0 error errs number errn end try return t end _join

I started setting this out manually, which soon brought the pattern to mind.

The combinations of tooling pieces used matches the 1s of all the binary numbers from 000000001 to 111111111, Making construction of a spreadsheet table showing all of the combinations (and their lengths) fairly simple. Here are the top and bottom few rows of such a table. Formulas are listed below.

Row 1 is a header row.

D1 - L1: These contain the lengths of each length of tooling, from longest to shortest.

N1, O1: Labels showing what's in these columns.

Row 2: All formulas are entered into this row, then filled down to row 512, where the binary count in column B reaches 111111111 (511 base 10)

B2: =ROW()-1 Format as number, base 2, nine digits.

C2: =B&" " Converts the binary number in B to a to character string by appending a space to the end.

D2: =IF(MID($C,COLUMN()-3,1)="1",D$1,0)

MID() extracts a single character from the string in C

IF compares that character with "1". If they match, the number in row 1 is inserted in the cell, if they do not match, a zero is inserted.

D2: Fill this formula right to L2

M2: Empty. Used as a separator.

N2: =SUM(D2:L2) Totals the lengths of tooling in this row.

O2: =COUNTIF(N$2:N2,N2) Counts the number of times the length in column N has been listed from the top row of the table to here.

Conditional Formatting: Before filling these formulas down, apply the following format rules. The rules will be copied to the rest of the cells in the column(s) when you fill down.

Select D2-L2. Use these two rules:

The first changes the text colour to a light grey when the cell contains a zero. Use white if you want the zero to be invisible.

The second changes the cell fill to yellow if the cell contains a number greater than zero.

This is the rule that puts an orange-red fill in column O cells when the length in N duplicates one earlier in the list.

I will keep a copy of this table for a while.If you'd like it sent to you, let me know via email. Hover the mouse on my name to seel and select my address.

Note that the table may not be sorted in its current form.

Regards,

Barry

Hello

Here's a slightly different version, which lists the same sum value with different combinations as well.

E.g., this script lists both combinations:

287 = 70 + 217 287 = 91 + 196

whilst the previous script lists only the former.

Regards,

H

_main() on _main() script o property |SEEDS| : {70, 91, 184, 196, 217, 330, 394, 835, 1670} property |MAX| : 2505 property pp : {} property qq : {} property rr : {} on cmp(x, y) (* comparator for msort handler *) x's item 1 > y's item 1 end cmp repeat with i from 1 to count my |SEEDS| set pp to combination(|SEEDS|, i) repeat with p in my pp set p to p's contents set q to sum(p) if q > |MAX| then -- skip this combination else set my qq's end to q set my rr's end to {q, p} end if end repeat end repeat msort(rr, cmp) --return {count rr, rr} -- for test repeat with r in (a reference to my rr) set r's contents to "" & r's item 1 & " = " & _join(r's item 2, " + ") -- N = A + B + ... --set r's contents to _join(r's item 2, " + ") & " = " & r's item 1 -- A + B + ... = N end repeat set r to _join(rr, linefeed) & linefeed set the clipboard to r return r end script tell o to run end _main on combination(xx, n) -- v1.02f3 (* list xx: list of items int n: number of items in each combination return list: list of combinations *) script o property aa : xx's contents property bb : {} property cc : {} property dd : {} if n = 0 then return {} if n = 1 then repeat with a in my aa set a to a's contents if {{a}} is not in my cc then set end of my cc to {a} end repeat return my cc's contents end if repeat (count my aa) - n + 1 times set a to my aa's item 1 set aa to my aa's rest if {a} is in my dd then -- prune this branch else set bb to combination(my aa, n - 1) repeat with b in my bb set end of my cc to {a} & b's contents end repeat set end of my dd to a -- add to prune list end if end repeat return my cc's contents end script tell o to run end combination on sum(xx) (* list xx : list of numbers return number : sum of numbers in xx *) set result to 0 repeat with x in xx result + x end repeat result end sum on msort(aa, cmp_) -- v1.2f2 (* Basic recursive merge sort handler having list sorted in place *) (* list aa : list to be sorted in place handler cmp_ : comparator * cmp_(x, y) must return true iff list element x and y are out of order. *) script o property parent : {} -- limit closure to minimum property xx : aa -- to be sorted in place property xxl : count my xx property yy : {} property cmp : cmp_ on merge(p, q, r) (* property xx: source list integer p, q, r : absolute indices to specify range to be merged such that xx's items p thru r is the target range, xx's items p thru (q-1) is the first sublist, xx's items q thru r is the second sublist. (p < q <= r) *) local i, j, k, xp, xr, yi, yj, ix, jx if r - p = 1 then set xp to my xx's item p set xr to my xx's item r if my cmp(xp, xr) then set my xx's item p to xr set my xx's item r to xp end if return -- exit else if p < q - 1 then merge(p, (p + q) div 2, q - 1) merge(q, (q + r + 1) div 2, r) end if (* At this point, sublits xx[p, q-1] and xx[q, r] have been already sorted (p < q <= r) *) if my cmp(my xx's item (q - 1), my xx's item q) then else -- xx[p, q-1] & xx[q, r] are already sorted return end if set yy to my xx's items p thru r -- working copy for comparison set ix to q - p set jx to r - p + 1 set i to 1 set j to q - p + 1 set k to p set yi to my yy's item i set yj to my yy's item j repeat if my cmp(yi, yj) then set my xx's item k to yj set j to j + 1 set k to k + 1 if j > jx then set my xx's item k to yi set i to i + 1 set k to k + 1 repeat until k > r set my xx's item k to my yy's item i set i to i + 1 set k to k + 1 end repeat return end if set yj to my yy's item j else set my xx's item k to yi set i to i + 1 set k to k + 1 if i > ix then set my xx's item k to yj set j to j + 1 set k to k + 1 repeat until k > r set my xx's item k to my yy's item j set j to j + 1 set k to k + 1 end repeat return end if set yi to my yy's item i end if end repeat end merge on _cmp_(x, y) (* primary comparator *) return x > y end _cmp_ if xxl ≤ 1 then return if cmp_ = {} then set my cmp to _cmp_ -- comparator fallback my merge(1, (xxl + 2) div 2, xxl) end script tell o to run end msort on _join(tt, d) (* list tt : source list string d : separator return string : tt joined with d *) local astid0, t try set {astid0, AppleScript's text item delimiters} to {AppleScript's text item delimiters, {} & d} set t to "" & tt set AppleScript's text item delimiters to astid0 on error errs number errn set AppleScript's text item delimiters to astid0 error errs number errn end try return t end _join

My pleasure! Glad to know it helps.

Do you think I have coded all of them in a few hours? No. Actually I have only coded the _main() handler this time. The rest are from my collection of handlers I have written years ago. 😉

By the way, you can customise the parameters at the beginning of _main() handler. Currently they're set as follows:

property |SEEDS| : {70, 91, 184, 196, 217, 330, 394, 835, 1670} property |MAX| : 2505

You can change them as you see fit.

Best wishes,

Hiroto

Hi Lewis,

Can do. You'll need to send me your email address, though. Mine is listed in my profile.

Regarding MAX value:

I didn't consider this, and used binaries to pull all the possible combinations including at least one of the lengths, so I included all the values from 000000001 to 111111111 (511). 2505 comes at 110000000 (384), so there's no need to continue the table past row 385.

Gathering the rest together (and grouping the duplicate pairs to choose which of each pair to keep) is best done by sorting the table on column N.

That requires first fixing the values in columns C and O by copying each column, then using the edit menu item Paste Values (or Paste Results, depending on version) to replace the formulas in these columns with the numbers they last calculated. Sorting on column N will then pull the pairs together (with the red flag beside them in column O), and place all of the 'extra length' combinations at the bottom of the list, where they may be deleted.

I would make a copy of the file before fixing values and sorting.

Regards,

Barry