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.

Advertisements

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 = [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: break
    
    $ python parts.py 2 3 4 6
    ([], 0, 0)
    ([2], 2, 26)
    ([4], 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).
      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:

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s

%d bloggers like this: