Jane’s Homework
December 12, 2017
Today’s exercise is from user Jane, who needs homework help:
Consider all partitionings of a list of positive integers into two partitions. For each partitioning, compute the sums of the two partitions, then compute the least common multiple of the two sums. Report the maximum of all possible least common multiples. For example, given the list (2 3 4 6), the possible partitionings, the associated sums, and the least common multiples, are:
() (2 3 4 6) - 0 15 - 0 (2) (3 4 6) - 2 13 - 26 (3) (2 4 6) - 3 12 - 12 (2 3) (4 6) - 5 10 - 10 (4) (2 3 6) - 4 11 - 44 (2 4) (3 6) - 6 9 - 18 (3 4) (2 6) - 7 8 - 56 (2 3 4) (6) - 9 6 - 18 (6) (2 3 4) - 6 9 - 18 (2 6) (3 4) - 8 7 - 56 (3 6) (2 4) - 9 6 - 18 (2 3 6) (4) - 11 4 - 44 (4 6) (2 3) - 10 5 - 10 (2 4 6) (3) - 12 3 - 12 (3 4 6) (2) - 13 2 - 26 (2 3 4 6) () - 15 0 - 0Thus, the maximum least common multiple is 56.
Jane writes that she wants to be able to recursively find all partitions given a list, and she thinks she will have to use lambda in her program.
Your task is to write a program that finds the maximum least common multiple of the part-sums of all possible 2-partitionings of a list of positive integers. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
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)))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 = [0]*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; if not found: breakHere’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]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.
#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). char* mask = (char*)calloc(n, sizeof(char)); 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[0]; focus[0] = 0; if (idx == n) break; focus[idx] = focus[idx+1]; focus[idx+1] = idx + 1; mask[idx] = !mask[idx]; if (mask[idx]) { 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); printf("%lu\n", answer); return 0; }Output:
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.
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))))))))