Programming Praxis

7 Responses to “Jane’s Homework”

1. Paul said

   December 12, 2017 at 9:43 PM

   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

   December 16, 2017 at 7:58 AM

   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

   December 18, 2017 at 2:32 AM

   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. r. clayton said

   December 28, 2017 at 10:16 PM

   A couple of solutions in Racket.
5. Daniel said

   January 29, 2018 at 3:54 AM

   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
   
6. Daniel said

   January 29, 2018 at 4:44 AM

   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.
7. Kevin said

   June 30, 2018 at 6:44 PM

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