## 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 2n possible 2-partitions. A simple binary code running from 0 to 2n − 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 kth `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

### 7 Responses to “Jane’s Homework”

1. Paul said

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

```from itertools import chain, combinations
from math import gcd

def partition2(arr):
'recursive method'
if not arr:
return [([], [])]
e, *rem = arr
res = []
for lft, rgt in partition2(rem):
res += [([e]+lft, rgt), (lft, [e]+rgt)]
return res

def lcm(a, b):
return a * b // gcd(a,b)

def powerset(iterable):
"powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
s = list(iterable)
return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

def partition3(arr):
c = list(powerset(arr))
return [(f, r) for f, r in zip(c, reversed(c))]

arr = [2, 3, 4, 6]
for i, (p0, p1) in enumerate(partition3(arr)):
s1, s2 = sum(p0), sum(p1)
print("{:2d} {:12s} {:12s} {:2d} {:2d}   {:2d}".\
format(i, str(p0), str(p1), s1, s2, lcm(s1, s2)))
```
2. matthew said

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

```import sys
from fractions import gcd

a = [int(s) for s in sys.argv[1:]]
s = sum(a); limit = s//2;
total = 0; c = *len(a)
maxlcm = -1

def lcm(a,b): return a//gcd(a,b)*b

while True:
l = lcm(total,s-total)
if l > maxlcm:
maxlcm = l
selected = [a[j] for j in range(len(a)) if c[j] != 0]
print(selected,total,l)
found = False
for i in range(len(a)):
if c[i] == 0 and total + a[i] <= limit:
total += a[i]; c[i] += 1
found = True; break
total -= c[i]*a[i]; c[i] = 0;
```
```\$ python parts.py 2 3 4 6
([], 0, 0)
(, 2, 26)
(, 4, 44)
([3, 4], 7, 56)
```
3. Globules said

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.

```import Control.Monad (replicateM)
import Data.Bifunctor (bimap)
import Data.Either (partitionEithers)
import Data.Function ((&))
import Data.List.NonEmpty (NonEmpty, fromList, toList)

-- All partitions of a list into two sub-lists, in which the original order of
-- the elements is retained.
part2s :: [a] -> [([a], [a])]
part2s xs = let es = replicateM (length xs) [Left, Right]
in map (partitionEithers . zipWith (&) xs) es

-- Split a non-empty list into all partitions consisting of two sub-lists, take
-- the lcm of the sums of the pairs of sub-lists, finally returning the maximum
-- of the lcms.
maxLcm :: Integral a => NonEmpty a -> a
maxLcm = maximum . map (uncurry lcm . bimap sum sum) . part2s . toList

main :: IO ()
main = print \$ maxLcm \$ fromList [2, 3, 4, 6]
```
```\$ ./jane
56
```
4. Daniel said

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.

```#include <stdio.h>
#include <stdlib.h>

// Euclid's algorithm (division-based)
unsigned long calc_gcd(unsigned long a, unsigned long b) {
while (b != 0) {
unsigned long tmp = b;
b = a % b;
a = tmp;
}
return a;
}

unsigned long calc_janes_homework(unsigned int* array, size_t n) {
unsigned long sum_partition_1 = 0;
unsigned long sum_partition_2 = 0;
for (size_t i = 0; i < n; ++i) {
sum_partition_2 += array[i];
}
unsigned long max_lcm = 0;
// Iterate over the power set by adding or removing one element
// at a time (using Loopless Gray binary generation).
size_t* focus = (size_t*)malloc(sizeof(size_t) * (n+1));
for (size_t i = 0; i < (n+1); ++i) {
focus[i] = i;
}
while (1) {
unsigned long gcd = calc_gcd(sum_partition_1, sum_partition_2);
unsigned long lcm = sum_partition_1 / gcd * sum_partition_2;
if (lcm > max_lcm) max_lcm = lcm;
size_t idx = focus;
focus = 0;
if (idx == n) break;
focus[idx] = focus[idx+1];
focus[idx+1] = idx + 1;
sum_partition_1 += array[idx];
sum_partition_2 -= array[idx];
} else {
sum_partition_1 -= array[idx];
sum_partition_2 += array[idx];
}
}
return max_lcm;
}

int main(void) {
unsigned int array[] = {2,3,4,6};
size_t n = sizeof(array) / sizeof(unsigned int);
unsigned long answer = calc_janes_homework(array, n);
return 0;
}
```

Output:

```56
```
5. Daniel said

I forgot to free the memory I allocated in the calc_janes_homework function. mask and focus should both be free’d before the function returns.

6. Kevin said

Here’s a solution in racket.

```(define (max-lcm ints)
(let sequencer ((max-lcm 0) (perms (permutations ints)))
(if (empty? perms)
max-lcm
(let parter ((seq-lcm 0) (i 0))
(if (> i (length ints))
(sequencer (max seq-lcm max-lcm) (cdr perms))
(let-values (((p1 p2) (split-at (car perms) i)))
(parter (max seq-lcm (lcm (apply + p1) (apply + p2))) (add1 i))))))))
```