## Jane’s Homework

### December 12, 2017

Let’s augment the table from the first page:

0 - 0000 - () (2 3 4 6) - 0 15 - 0 1 - 0001 - (2) (3 4 6) - 2 13 - 26 2 - 0010 - (3) (2 4 6) - 3 12 - 12 3 - 0011 - (2 3) (4 6) - 5 10 - 10 4 - 0100 - (4) (2 3 6) - 4 11 - 44 5 - 0101 - (2 4) (3 6) - 6 9 - 18 6 - 0110 - (3 4) (2 6) - 7 8 - 56 7 - 0111 - (2 3 4) (6) - 9 6 - 18 8 - 1000 - (6) (2 3 4) - 6 9 - 18 9 - 1001 - (2 6) (3 4) - 8 7 - 56 10 - 1010 - (3 6) (2 4) - 9 6 - 18 11 - 1011 - (2 3 6) (4) - 11 4 - 44 12 - 1100 - (4 6) (2 3) - 10 5 - 10 13 - 1101 - (2 4 6) (3) - 12 3 - 12 14 - 1110 - (3 4 6) (2) - 13 2 - 26 15 - 1111 - (2 3 4 6) () - 15 0 - 0

For a list of *n* items, there will be 2^{n} possible 2-partitions. A simple binary code running from 0 to 2^{n} − 1 specifies which list items to include in each partition:

(define (part k xs) (let loop ((ds (reverse (digits k 2))) (xs xs) (ys (list))) (if (null? ds) (reverse ys) (if (zero? (car ds)) (loop (cdr ds) (cdr xs) ys) (loop (cdr ds) (cdr xs) (cons (car xs) ys))))))

The *k*th `part`

takes the binary representation of *k* and applies it to *xs*, keeping those items with a 1-bit at that list item. Thus, to compute the 11th partition of (2 3 4 6), express 11 as 1011 in binary and keep the 2, 3 and 6 (the bits count right-to-left) of the input. The other partition, of course, is whatever is left. Then it’s easy to find the maximum least common multiple:

(define (max-lcm xs) (let ((len (length xs)) (tot (sum xs))) (apply max (map (lambda (s) (lcm s (- tot s))) (map sum (map (lambda (k) (part k xs)) (range (expt 2 (- len 1))))))))))

Reading from the inside out: `range`

generates a half-list of partition numbers (only half is needed due to symmetry), then `lambda (k)`

computes the partition, `sum`

sums the item in the partition, `lambda (s)`

computes the least common multiple of the partition-sum and its conjugate, and `max`

finds the maximum:

> (max-lcm '(2 3 4 6)) 56

You can run the program at https://ideone.com/c4yYG6.

Pages: 1 2

Two methods to partition, one recursive and the other using the powerset function from the itertools documentation.

Here’s another way: iteratively generate combinations but bail out when the combination sum gets too large (this works for any value of limit and it’s straightforward to generalize to multisets):

Here’s a Haskell version that doesn’t use explicit recursion. The part2s

function uses replicateM (the monadic version of replicate, for lists) to

generate all length 4 (in our example) combinations of Left and Right, the two

constructors for Either. For each combination we zip it with the original list,

using the “reverse application operator”, to produce a list of Eithers which is

then partitioned into two lists.

A couple of solutions in Racket.

Here’s a solution in C.

The code iterates over the power set of the input list. The approach is based on Loopless Gray binary generation (Algorithm L in TAOCP section 7.2.1.1), which calculates a single element index to be added or removed on each iteration. Partition sums are re-calculated with an addition or subtraction of the updated element. LCM is then calculated on these updated sums.

Output:

I forgot to free the memory I allocated in the calc_janes_homework function.

maskandfocusshould both be free’d before the function returns.